Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
public static bool Matches(string text, string pattern)
{
if (text == string.Empty && pattern == string.Empty)
return true;
int i = 0;
for (; i < pattern.Length && i<text.Length; i++)
{
if (pattern[i] == '*')
{
return Matches(text.Substring(i + 1), pattern.Substring(i)) || Matches(text.Substring(i + 1), pattern.Substring(i+1));
}
if(text[i] != pattern[i])
return false;
}
if (text.Length - 1 >= i || pattern.Length - 1 >= i)
return false;
return true;
}
static bool Match(string p, string s)
{
if (string.IsNullOrEmpty(p))
{
throw new ArgumentNullException("pattern cannot be null or empty");
}
int i = 0;
while (p[i] != '*')
{
if (i >= s.Length || p[i] != s[i])
{
return false;
}
i++;
if (i == p.Length)
{
throw new ArgumentException("Pattern doesn't have *");
}
}
if (s.Length - i < p.Length - 1 - i)
{
return false; // s doesn't have enough leftover to compare
}
// Compare everything behind the *
for (int j = 0; j < p.Length - 1 - i; j++)
{
if (p[p.Length - j - 1] == '*')
{
throw new ArgumentException("multiple *s detected");
}
if (s[s.Length - j - 1] != p[p.Length - j - 1])
{
return false;
}
}
return true;
}
public static boolean matches(String fileName, String singleStarPattern) throws FileNameFormatException, singleStarPatternFormatException {
if(fileName.contains("*"))
return false;
if(singleStarPattern.indexOf("*") != singleStarPattern.lastIndexOf("*") || !singleStarPattern.contains("*"))
return false;
int startRun = 0;
while (fileName.charAt(startRun) == singleStarPattern.charAt(startRun))
startRun++;
int endRun = singleStarPattern.length() - 1;
int run = fileName.length() - 1;
while (fileName.charAt(run) == singleStarPattern.charAt(endRun))
{
run --;
endRun --;
}
return startRun == endRun;
}
Algo: regex_matcher(s1, s2)
1. if s1 and s2 are empty return true
2. if *s1 and *s2 are same recurse for rest of the strings
3. if in wildcard string(s2) we find * we have option of skipping it and going ahead with next character or match one character in s1 and recurse
4. if none of the above matches return false
#include<iostream>
using namespace std;
bool regex_matcher(char *s1, char *s2)
{
if(!*s1 && !*s2)
return true;
if(*s2 == '*' && *(s2+1) != '\0' && *s1 == '\0')
return false;
if(*s1 == *s2)
return regex_matcher(s1+1, s2+1);
if(*s2 == '*')
return (regex_matcher(s1, s2+1) || regex_matcher(s1+1, s2));
return false;
}
int main()
{
bool matched = regex_matcher("index.html", "i*************x.htm*");
if(matched)
cout<<"matched"<<endl;
else
cout<<"not matched"<<endl;
return 0;
}
boolean isMatch(String src, String pattern)
{
int src_index =0;
int pattern_index = 0;
while(src_index < src.length() && pattern_index < pattern.length())
{
if(pattern.charAt(pattern_index)=='*')
{
if(pattern_index+1 < pattern.length())
{
pattern_index++;
while(src_index < src.length() && src.charAt(src_index)!=pattern.charAt(pattern_index))
{
src_index++;
}
if(src_index >= src.length())
return false;
}
else
{
return true;
}
}
else
{
pattern_index++;
src_index++;
}
}
if(pattern_index < pattern.length() || src_index < src.length())
return false;
else
return true;
}
boolean isMatch(String src, String pattern)
{
int src_index =0;
int pattern_index = 0;
while(src_index < src.length() && pattern_index < pattern.length())
{
if(pattern.charAt(pattern_index)=='*')
{
if(pattern_index+1 < pattern.length())
{
pattern_index++;
while(src_index < src.length() && src.charAt(src_index)!=pattern.charAt(pattern_index))
{
src_index++;
}
if(src_index >= src.length())
return false;
}
else
{
return true;
}
}
else
{
pattern_index++;
src_index++;
}
}
if(pattern_index < pattern.length() || src_index < src.length())
return false;
else
return true;
}
public static boolean matches(String text , String pattern){
int p_length = 0;
for (int i = 0 ;i<pattern.length();++i){
if (pattern.charAt(i)!='*'){
p_length++;
}
}
int i = 0 , j = 0;
int txt_length = 0;
boolean consecutive = false;
while (i<text.length()&&j<pattern.length()){
if (pattern.charAt(j)=='*'){
j++;
}else{
if (text.charAt(i)!=pattern.charAt(j)){
if (consecutive){
return false;
}
}else{
j++;
txt_length++;
consecutive = true;
}
}
i++;
}
return txt_length==p_length;
}
It seems to me this is mainly about catching all the "edge cases." I think I got them all but maybe not:
def match(str, pattern):
if str != "" and pattern == "":
return False
if str == "" and pattern == "":
return True
if str == "" and pattern == "*":
return True
if pattern[0] == "*" and len(str) == 1 and len(pattern) > 1:
return False
if pattern[0] == str[0]:
return match(str[1:], pattern[1:])
if pattern[0] == "*":
return match(str[1:], pattern) or match(str, pattern[1:])
return False
The recursive version that many have posted is elegant but not efficient since it performs backtracking. We can match any regex in a single scan, although it may be tricky. In my case, it was just a lot of tricky edge cases.
Here's my shot at it:
public static Boolean match(String string, String pattern) {
int strIdx = 0;
int patIdx = 0;
int starIdx = -1;
while(true) {
if (strIdx == string.length()) {
if (patIdx == pattern.length()) return true;
else if (pattern.charAt(patIdx) == '*') {
if (patIdx == pattern.length()-1) return true;
else {
patIdx++;
continue;
}
}
else return false;
}
else if (patIdx == pattern.length()) {
return false;
}
else if (pattern.charAt(patIdx) == '*') {
if (patIdx == pattern.length()-1) return true;
starIdx = patIdx;
patIdx++;
}
else if (string.charAt(strIdx) != pattern.charAt(patIdx)) {
if (starIdx != -1) {
patIdx = starIdx+1;
strIdx++;
}
else return false;
}
else {
strIdx++;
patIdx++;
}
}
}
private boolean matches(String text, String pattern) {
if (text == null && pattern == null) return true;
if ((text != null && pattern == null) || (text==null && pattern!=null) ) return false;
for (int i=0;i<text.length()&&i<pattern.length();i++) {
if(pattern.charAt(i) == '*') {
return text.contains(pattern.substring(i+1));
} else (pattern.charAt(i) == text.charAt(i)) {
return matches(text.substring(i + 1), pattern.substring(i + 1));
}
}
return false;
}
static bool matches(string input, string pattern)
{
bool matches = true;
if (pattern.Count(c => c == '*') != 1)
return false;
var parts = pattern.Split('*');
if (parts.Length != 2)
return false;
bool isLeftSideNotEmpty = !String.IsNullOrEmpty(parts[0]);
bool isRightSideNotEmpty = !String.IsNullOrEmpty(parts[1]);
if (isLeftSideNotEmpty)
{
matches &= input.StartsWith(parts[0]);
}
if (isRightSideNotEmpty)
{
matches &= input.EndsWith(parts[1]);
}
Console.WriteLine(matches);
return matches;
}
we just have to find whether the left hand side string of * is a prefix and right hand size is a suffix. then we will need to find whether suffix.length + prefix.length < original_string.length or not. If * also allows blank characters we even will not need this check.
we have to assume that blank "" character is always a prefix and suffix.
/*
Check if a given file name match a single-star pattern? (can't use regex I)
index.html matches *.html
foo.txt does not match *.html
matches("index.html", "*html") returns true
matches("foo.txt", "*html") returns false
matches("cat", "c*t") returns true
*/
public class Solution {
public static void main(String ... args) {
Solution sol = new Solution();
System.out.println(sol.isMatch("*", "hello.txt"));
System.out.println(sol.isMatch("he*", "hello.txt"));
System.out.println(sol.isMatch("*txt", "hello.txt"));
System.out.println(sol.isMatch("he*xt", "hello.txt"));
System.out.println(sol.isMatch("xx*", "hello.txt"));
}
private boolean isMatch(String singleStarPattern, String filename) {
int starIndex = singleStarPattern.indexOf("*");
if(starIndex == -1) { throw new IllegalArgumentException("Invalid pattern"); }
else if (singleStarPattern.length()==1) {return true;} // * matches everything
String prefix = singleStarPattern.substring(0, starIndex);
String suffix = singleStarPattern.substring(starIndex+1);
boolean prefixMatches=false, suffixMatches=false;
if(prefix.length()==0 || filename.startsWith(prefix)) { prefixMatches=true; }
if(suffix.length()==0 || filename.endsWith(suffix)) { suffixMatches=true; }
return prefixMatches && suffixMatches;
}
}
/*
Check if a given file name match a single-star pattern? (can't use regex I)
index.html matches *.html
foo.txt does not match *.html
matches("index.html", "*html") returns true
matches("foo.txt", "*html") returns false
matches("cat", "c*t") returns true
*/
public class Solution {
public static void main(String ... args) {
Solution sol = new Solution();
System.out.println(sol.isMatch("*", "hello.txt"));
System.out.println(sol.isMatch("he*", "hello.txt"));
System.out.println(sol.isMatch("*txt", "hello.txt"));
System.out.println(sol.isMatch("he*xt", "hello.txt"));
System.out.println(sol.isMatch("xx*", "hello.txt"));
}
private boolean isMatch(String singleStarPattern, String filename) {
int starIndex = singleStarPattern.indexOf("*");
if(starIndex == -1) { throw new IllegalArgumentException("Invalid pattern"); }
else if (singleStarPattern.length()==1) {return true;} // * matches everything
String prefix = singleStarPattern.substring(0, starIndex);
String suffix = singleStarPattern.substring(starIndex+1);
boolean prefixMatches=false, suffixMatches=false;
if(prefix.length()==0 || filename.startsWith(prefix)) { prefixMatches=true; }
if(suffix.length()==0 || filename.endsWith(suffix)) { suffixMatches=true; }
return prefixMatches && suffixMatches;
}
}
If it is only one star, then only need to compare if the star & end equals the two parts in the pattern seperated by "*".
1. String[] strArr= pattern.split("\\*"); get two patterns for 'start with' and 'end with'.
2. just see if the string is start with strArr[0], and end with strArr[1].
3. some special cases, like empty...
In English (for the lazy), take the piece(s) of the query that are before, between, and after the wildcards, ie just the pieces that are not the wildcard, and strstr them in order against the body string. If / when you find a match for a piece, continue strstr'ing the next piece from the end of that match. This is O(N).
java code:
I assumed that if there is no star in the second String, false should be returned.
static boolean matches(String input, String star) {
if (star.length()==0) return false;
int p=0, q=0;
while (p < input.length() && q < star.length() && star.charAt(q)!='*') {
//Move from begin to end until hit '*'
if (input.charAt(p++) != star.charAt(q++)) return false;
}
if (q==star.length()) //q==star.length() means no '*' in star
return false;
int u=input.length()-1, v=star.length()-1;
while (u >= 0 && v >= 0 && star.charAt(v) != '*') {
//Move from end to begin until hit '*'
if (input.charAt(u--) != star.charAt(v--)) return false;
}
if (v < 0) //v<0 means no '*' in star
return false;
//If there is a match with a single '*' in star
//q and v should both end up at the position of '*'
return q==v && star.charAt(q)=='*' && star.charAt(v)=='*';
}
Test cases:
"", "": false
"", "*": true
"abcde", "*": true
"abcde", "a*e": true
"abcde", "abc*de": true
"abcde", "*e": true
"abcde", "a*": true
"aaaaaaaaaa", "aa": false
"abababab", "ab": false
"abababab", "ab*b": true
"abababab", "ab***ab": false
- Nit January 19, 2014