Monday, June 2, 2014

LeetCode Regular Expression Match

It always to get the time limited exceed.
Skipping some cases can avoid the situation.

public boolean isMatch(String s, String p) {
        //I have the boundary condition
//although it is easy to follow
   if(s.length()==0)
            return p.length()>1 && p.length()%2==0 ? p.charAt(1)== '*'
                && isMatch(s,p.substring(2)) : p.length()==0;
if (p.isEmpty()) return false;

char c1 = s.charAt(0);
char c2 = p.charAt(0);
char c2next = p.length() > 1 ? p.charAt(1) : 'x';
if (c2next == '*') {
if (isSame(c1,c2)) {
return isMatch(s.substring(1), p) || isMatch(s, p.substring(2));
} else {
return isMatch(s,p.substring(2));
}
} else {
if (isSame(c1,c2)) {
return isMatch(s.substring(1),p.substring(1));
} else {
return false;
}
}

}
private static boolean isSame(char c1, char c2) {
return c2 == '.' || c1==c2;
}

No comments:

Post a Comment