Solution to LeetCode Regular Expression Matching problem.
The solution is separated into a couple of different cases. One case is the pattern .*, another is l* where l is any letter, .l, and ll. Use two pointers – iptr for the input pointer, and rptr, for the regex pointer.
public boolean isMatch(String s, String p) {
return match(s.toCharArray(), p.toCharArray(), 0, 0);
}
private boolean match(char[] input, char[] regex, int iptr, int rptr){
if(rptr >= regex.length && iptr >= input.length) return true; // both exhausted
if(rptr >= regex.length && iptr < input.length) return false;
// Next character is a *. Current character is either a '.' or a letter
if(rptr < regex.length - 1 && regex[rptr+1] == '*'){
if(iptr >= input.length) return match(input,regex,iptr,rptr+2); // empty string, keep matching
if(regex[rptr] == '.'){ // it's a dot. Match anything
// Skip the .* pattern or select the current letter and stay on .*
return match(input,regex,iptr,rptr+2) || match(input,regex,iptr+1,rptr);
}
else{ // current char must a letter
// Skip the l* pattern or if it matches, skip over the letter
return match(input,regex,iptr,rptr+2) || (regex[rptr] == input[iptr] && match(input,regex,iptr+1,rptr));
}
} else if(regex[rptr] == '.'){ // current is '.', but next is a letter
if(iptr >= input.length) return false; // out of input
return match(input,regex,iptr+1,rptr+1); // advance both pointers
} else{ // current and next are characters
if(iptr >= input.length) return false; // out of input
// if the characters are equal, go forward
if(regex[rptr] == input[iptr]) return match(input,regex,iptr+1,rptr+1);
}
return false; // nothing matched
}