Tuesday, October 7, 2014

[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;
       }
   }
}

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

No comments:

Post a Comment