[Dream Big, Think Big, Achieve Big!] Regex 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;

}

}

......