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") → 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

.表示内容，匹配任意字符。

*表示数字，匹配前面的0个或者任意多个字符。

核心思路是：

每次我们看pattern的时候，看2个。

可以分为2种情况。

1. a* 这种，第二个字符是*

这个时候，我们看第一个字符，如果s中的当前第一个字符和p的当前第一个字符不相等，那么我们只能表示0个匹配。

比如s = 'b' p = 'a*b',pattern中的'a*'匹配0个a，相当于继续看后面的s = 'b',p = 'b'。

如果当前字符相等，表示匹配是合法的。

这时候，我们可以选择匹配0个，也可以选择匹配1个。

如果s后面的字符依旧相等，我们可以继续匹配2个...

然后看后面的匹配（利用递归）

2. aa 这种，第二字符不是*

第2种是好办的，如果pattern不是'.'，且2个字符不相等的话，直接返回false了。

如果相当，继续看后面的匹配（利用递归）

递归的终止条件：

1. s 和p都匹配到了最末尾。说明匹配成功

2. p匹配到了最末尾，s没有，说明匹配失败

3. s匹配到了最末尾，p没有，p后面跟着a*这类的，我们可以匹配0个，还可以继续匹配，否则就是匹配失败了。

运行时间：

代码：

public class RegularExpressionMatching {
    public boolean isMatch(String s,String p) {
        return doMatch(s,p,0);
    }

    private boolean doMatch(String s,int sIndex,String p,int pIndex) {
        if (sIndex == s.length() && pIndex == p.length()) {
            return true;
        }
        if (pIndex == p.length()) {
            return false;
        }
        if (sIndex == s.length()) {
            if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*') {
                return doMatch(s,sIndex,pIndex + 2);
            }
            else {
                return false;
            }
        }
        if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*') {
            if (p.charAt(pIndex) != '.' && s.charAt(sIndex) != p.charAt(pIndex)) {
                return doMatch(s,pIndex + 2);
            }
            if (doMatch(s,pIndex + 2)) {
                return true;
            }
            for (int i = sIndex; i < s.length(); i++) {
                boolean result = false;
                if (p.charAt(pIndex) == '.' || s.charAt(i) == p.charAt(pIndex)) {
                    result = doMatch(s,i + 1,pIndex + 2);
                    if (result) {
                        return true;
                    }
                } else {
                    return false;
                }
            }
        } else {
            if (p.charAt(pIndex) == '.' || p.charAt(pIndex) == s.charAt(sIndex)) {
                return doMatch(s,sIndex + 1,pIndex + 1);
            } else {
                return false;
            }
        }
        return false;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!