154. Regular Expression Matching & 192. Wild Card Matching

  1. 注意这题是reg exp,不是wildcard matching。两者最大的区别就是在于对于a*的匹配。wild card matching遇到a*是必须有a在前面的。而reg情况下a*可以和一个空字符match。
  2. wildcard目前掌握的是一个非递归的带回溯的算法,私以为已经很不错了,这里reg的需要递归地来做。
  3. 主要的分水岭就是看那个带星号的空串匹配。然后适当地找到已匹配了的长度,去掉以后再递归匹配之后的字符串。
  4. 这题我是没能想出来这么牛的做法。思路如下,先看是否当前p是长度为1或者第二个字符不是*。
  5. if yes,那么这就是第一种判断情形。即之比较两个字符串的第一个字符,然后再递归处理剩下的。先看否定情况。即如果s为null或者p的第一个字符不匹配s第一个字符(即两个字符不相等且p[0]也不是‘.’)直接返回false。其他情况要再讨论,递归比较两个去掉首字符的子串。
  6. if no, 就是说p的第二个是*, 需要循环地调用递归来判断s的各种子串和p去掉前两个字符的子串。循环体是i从-1到小于len,为啥是-1。因为子串是s.substring(i+1)才能保证去掉当前字符的后面的子串。这样就cover了从0开始的子串,所以还要特殊在循环条件里写上i<0的时候的判断不能直接调用比较s[i]。
  7. 具体代码如下

public boolean isMatch(String s, String p) {
 // write your code here
 
 if(p==null||p.length()==0){
 return s.length()==0;
 }
 if(p.length()==1 || p.charAt(1) != ‘*’){
 if(s==null||s.length()==0 || s.charAt(0)!=p.charAt(0) && p.charAt(0)!=’.’)
 return false;
 
 return isMatch(s.substring(1), p.substring(1));
 }
 else{
 int i=-1;
 while(i<s.length() && (i<0 || (s.charAt(i) == p.charAt(0) ||p.charAt(0)==’.’)) ){
 if(isMatch(s.substring(i+1), p.substring(2))){
 return true;
 }
 i++;
 }
 return false;
 }
 
 
 }

while(i<s.length()){
 if(j<p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j)==’?’)){
 i++;
 j++;
 }
 else if(j<p.length() && p.charAt(j) == ‘*’){
 while(j<p.length() && p.charAt(j)==’*’){
 j++;
 }
 if(j==p.length()){
 return true;
 }
 back = true;
 backS = i;
 backP = j;
 }
 else if(back){
 i = ++backS;
 j = backP; 
 }
 
 else{
 return false;
 }
 }
 
 while(j<p.length() && p.charAt(j)==’*’){
 j++;
 }
 
 
 return j==p.length();

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.