[Dream Big, Think Big, Achieve Big!] Regular Expression Matching Problems 2

包子IT面试培训 助你拿到理想的offer! 

有问题，问包子！Got question? Ask Baozi!

接着上一轮关于regex的博客讨论，下面我们讨论一下另一道比较常见的regular expression matching问题，来自于leetcode.com

[例题2]

'.' 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") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "a*") → true

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true

[思路]

这道题乍看很简单，就是把String和Pattern里的字符一个一个match就行了，当遇到.时就可以替换任何字符。但问题是当遇到*时，比如a*，应该替换String里多少a呢？尤其是Pattern里有这种组合时: .* 情况就更复杂了很难马上知道应该替换多少字符。

这样就可以使用我们刚才提到的recursion的方式，对于每一种可能的替换，我们都尝试匹配。

因为题目要求返回true or false来表示是否找到全string匹配，我们可以定义recursion function为

boolean match(String s, int i, String p, int j)

当遇到当S匹配到i，P匹配到j，并且p[j]==’.’ p[j+1]==’*’时，我们尝试s里从i的任何匹配

for(int itr = i; itr < s.length(); itr++){

if(match(s, itr, p, j+2)){

return true;

}

}

这里注意两点

1) itr 从i 开始向下一层recursion传。因为*可以代表0个前面字符，所以.*可以不匹配任何字符

2) itr  < s.length()而不是(s.length() - (p.length() - j))，因为p剩下的字符依然可能是.*组合，我们在的现在并不知道，所以依然要匹配到s.length()

[代码]

public class Solution {
   public boolean isMatch(String s, String p) {
       assert(p!=null && (p.length()==0 || p.charAt(0)!='*'));
       
       if(p.length()==0) return s.length()==0;
       
       if(p.length()==1 || p.charAt(1)!='*'){
           if(s.length()<1 || (p.charAt(0)!='.' && p.charAt(0)!=s.charAt(0)))
               return false;
           return isMatch(s.substring(1),p.substring(1));
       }else{
           int i=-1;
           while(i<s.length() && (i<0 || p.charAt(0)=='.' || p.charAt(0)==s.charAt(i))){
               if(isMatch(s.substring(i+1),p.substring(2)))
                   return true;
               i++;
           }
           return false;
       }
   }
}

代码和我们分析时不同，这样为了更加简洁