首页 > 代码库 > Leetcode: Regular Expression Matching
Leetcode: Regular Expression Matching
Implement regular expression matching with support for ‘.‘ and ‘*‘.‘.‘ Matches any single character.‘*‘ Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true
难度：100，情况分得太多太细，跟Wildcard Matching很像又比那个难多了，很难在面试那么短的时间内理清思路，参考了Code Ganker的思路。
在这个题里面，假设我们维护一个布尔数组res[i][j],代表s的前i个字符和p的前j个字符是否匹配(注意这里res的维度是s.length()+1,p.length()+1)。递推公式跟上面类似，分三种种情况：
(1)p.charAt(j)不是‘*‘。情况比较简单，只要判断如果当前s的i和p的j上的字符一样（如果有p在j上的字符是‘.‘,也是相同），并且res[i][j]==true，则res[i+1][j+1]也为true; res[i][j]==false, res[i+1][j+1]也为false
(2)p.charAt(j)是‘*‘，但是p.charAt(j-1) != ‘.‘。那么只要以下条件有一个满足即可对res[i+1][j+1]赋值为true：
1)res[i+1][j]为真（‘*‘只取前面字符一次）;
2)res[i+1][j-1]为真（‘*‘前面字符一次都不取，也就是忽略这两个字符）;
3)res[i][j+1] && s.charAt(i)==s.charAt(i-1) && s.charAt(j-1)==p.charAt(j-1) (这种情况是相当于i从0到s.length()扫过来，如果p[j+1]对应的字符是‘*’那就意味着接下来的串就可以依次匹配下来，如果下面的字符一直重复，并且就是‘*’前面的那个字符）。
(3)p.charAt(j)是‘*‘，并且p.charAt(j-1) == ‘.‘。因为".*"可以匹配任意字符串，所以在前面的res[i+1][j-1]或者res[i+1][j]中只要有i+1是true，那么剩下的res[i+1][j+1],res[i+2][j+1],...,res[s.length()][j+1]就都是true了。
这道题有个很重要的点，就是实现的时候外层循环应该是p,然后待匹配串s内层循环扫过来。
1 public boolean isMatch(String s, String p) { 2 if(s.length()==0 && p.length()==0) 3 return true; 4 if(p.length()==0) 5 return false; 6 boolean[][] res = new boolean[s.length()+1][p.length()+1]; 7 res[0][0] = true; 8 for(int j=0;j<p.length();j++) //Outer circle is p, so scan the column first 9 {10 if(p.charAt(j)==‘*‘) //if this column of p is ‘*‘11 {12 if(j>0 && res[0][j-1]) res[0][j+1]=true; //the first row of this column, start fill res[][] from colum 213 if(j<1) continue; //all elements of column 0 and 1 should be false, except res[0][0], 14 if(p.charAt(j-1)!=‘.‘) //the case where p.charAt(j)==‘*‘,and p.charAt(j-1)!=‘.‘15 {16 for(int i=0;i<s.length();i++)17 {18 if(res[i+1][j] || j>0&&res[i+1][j-1] 19 || i>0 && j>0 && res[i][j+1]&&s.charAt(i)==s.charAt(i-1)&&s.charAt(i-1)==p.charAt(j-1))20 res[i+1][j+1] = true;21 }22 }23 else // case where p.charAt(j)==‘*‘ and p.charAt(j-1)==‘.‘ 24 {25 int i=0;26 while(j>0 && i<s.length() && !res[i+1][j-1] && !res[i+1][j])27 i++;28 for(;i<s.length();i++) //since this i, all elements down this column are true29 {30 res[i+1][j+1] = true;31 }32 }33 }34 else // case where p.charAt(j) != ‘*‘, general cases, compare s.charAt(i) with p.charAt(j)35 {36 for(int i=0;i<s.length();i++)37 {38 if(s.charAt(i)==p.charAt(j) || p.charAt(j)==‘.‘)39 res[i+1][j+1] = res[i][j];40 }41 }42 }43 return res[s.length()][p.length()];44 }
Leetcode: Regular Expression Matching