'*' star matches zero or more preceding characters
'.' each dot matches exactly one character
'^' prefix match, meaning that input string must start with exactly the same string following '^', e.g., '^abc' will match 'abcdefg', but 'cdefg' doesn't.
'$' suffix match, meaning that input string must end with exactly the same string following '$', e.g., '$abc' will match 'cdefgabc', but 'abcdefg' doesn't
without any special character: return True if pattern is in string (contains, not exactly same), and False otherwise
# Your code here
Naive Way: This question is really hard in that it requires to match exactly part of the string. And it doesn't need to start from beginning of the string. I am assuming that ^ and $ will always appear as the first character of pattern and either of them will appear or nor of them appear.
My brute force way to match from every possible position. Use a recursive matching.
public class Solution{
public static void main(String args[]){
Solution s = new Solution();
System.out.println(s.match("aabab",".*bab"));
}
public boolean match(String string, String pattern){
// edge case
if(pattern==null || pattern.length()==0) return string==null || string.length()==0;
if(string==null || string.length()==0) return pattern==null || pattern.length()==0;
// get suffix and prefix
boolean isPrefixed = false, isSuffixed = false;
if(pattern.charAt(0)=='^') isPrefixed = true;
if(pattern.charAt(0)=='$') isSuffixed = true;
// main process
char[] s = string.toCharArray();
char[] p = pattern.toCharArray();
if(isPrefixed) return match(s, 0, p, 1, -1);
else if(isSuffixed){
for(int i = 1;i < s.length;i++)
if(match(s,i,p,1,1)) return true;
}else{
for(int i = 0;i < s.length;i++){
if(i==0 && match(s,i,p,0,-1)) return true;
else if(i!=0 && match(s,i,p,0,0)) return true;
}
}
return false;
}
private boolean match(char[] string, int index1, char[] pattern, int index2, int matchEnd){
// ending case
if(index2 == pattern.length){
if(matchEnd==1) return index1==string.length;
else if(matchEnd==-1) return index1 < string.length;
else return true;
}
if(index1 < 0 || index1 >= string.length || index2 >= pattern.length) return false;
int i = index1, j = index2;
if(string[i] == pattern[j] || pattern[j] == '.') return match(string, i+1, pattern, j+1, matchEnd);
else if(j+1 < pattern.length && pattern[j+1] == '*') return match(string, i, pattern, j+2, matchEnd);
else if(pattern[j] == '*'){
int u = i-2;
while(u < string.length && (u==i-2 || string[u] == pattern[j-1] || pattern[j-1] == '.'))
if(match(string, u++, pattern, j+1, matchEnd)) return true;
}
return false;
}
}
