Google Interview Question
SDE1sCountry: United States
There could be DP approach. f[i][j] = true / false (can we parse first j characters of the string with first i characters of the regexp). We also can represent regexp as automata, but that is optional.
public class RegexMatch {
public static boolean matches(String pat, String str){
int patlen = pat.length();
int strlen = str.length();
if(patlen == 0) return strlen == 0;
char patFirst = pat.charAt(0) ;
if(patlen == 1 ){
return strlen == 1 && charsMatch(patFirst, str.charAt(0));
}
char patSecond = pat.charAt(1);
if( patSecond != '+' && patSecond != '*'){ // just a character
return strlen > 0 && charsMatch(patFirst, str.charAt(0))
&& matches(pat.substring(1), str.substring(1));
} else {
if(patSecond == '*'){
return (strlen > 0 && charsMatch(str.charAt(0),patFirst)
&& matches(pat, str.substring(1))
|| matches(pat.substring(2), str));
} else { // +
return strlen > 0 && charsMatch(str.charAt(0),patFirst) &&
matches("" + patFirst +'*' + pat.substring(2), str.substring(1));
}
}
}
private static boolean charsMatch(char ch1, char ch2){
if(ch1 == '.' || ch2 == '.') return true;
return ch1 == ch2;
}
public static void main(String[] args) {
test("ac*a*ca", "aca");
test("ac+a*ca", "aca");
test("ac*a*ca", "acaca");
test("ac+a*ca", "acaca");
test("ac+a+ca", "acaca");
test("ac*a*cab", "acaca");
test(".+a", "acaca");
test(".+b", "acaca");
test(".*world!+", "hello world!!!");
test(".*woald!+", "hello world!!!");
}
private static void test(String pattern, String str) {
System.out.println("String " + str+ " matches pattern " + pattern +": " + matches(pattern, str));
}
}
I am not good at dynamic programming, so the border conditions may not be true
Let String is s
and Pattern p
for . or character
if (p[j] == '.' || s[i] == p[j]) {
DP[i+1][j+1] = DP[i][j];
} else if (p[i] == '+') {
DP[i+1][j+1] = DP[i][j+1] || DP[i+1][j];
} else if (p[i] == '*') {
// do back track as we may have already consider pattern like c*(c already matched)
DP[i][j] = DP[i-1][j] || DP[i][j-1];
} else {
DP[i+1][j+1] = false;
}
This is written in Go:
- Julian January 28, 2014