博客

题目：实现支持’.’和”*”的正则表达式匹配

‘.’匹配任意一个字母

‘*’匹配0个或者多个前面的字符。

匹配应该覆盖整个输入字符串而不是仅仅一部分。如字符串“aaa”与模式”a.a”和”ab*ac*a”匹配，而与”aa.a”及”ab*a”均不匹配。

思路：首先要理解题意（想了好久才了解这个题目的意思）。这个说的是两个字符串要完全相等。意思就是判断是否能用含有’.’和”*”的字符串（我们称模式）来完全代替另一个字符串（我们称原串）。

（1）当原串为空时，显然只有模式串为空，或者具有“X*X*”的形式可以代替原串。

（2）当原串不为空，而模式串为空，显然false

（3）当原串不为空，模式串也不为空。

如果模式串第二个字符为”*”：如果模式串第一个字符与原串第一个字符相等，那么两者都可以进2；如果两者第一个字符不相等，那么只能模式串进2；

如果模式串第二个字符不为”*”：如果模式串第一个字符与原串第一个字符相等，那都可以进1；否则必然不能代替原串，返回false.

代码用递归的方式实现：

bool isMatch(string s, string p) {
        // write your code here
        //注意：'*'是匹配'*'之前的字符,匹配0个字符指的是前面的字符为0，即删去前面的字符
        //匹配,要两个字符串完全相等。意思就是判断是否能用含有'.'或"*"的字符串代替另一个字符串
        if (s.length() == 0){
            // s串匹配完合法的情况只有p为空，或是 "X*X*"的形式
            if (p.length() & 1) return false;
            else {
                for (int i = 1; i < p.length(); i += 2) {
                    if (p[i] != '*') return false;
                }
            }
            return true;
        }
        if (p.length() == 0) return false;
        if (p.length() > 1 && p[1] == '*') {
            if (p[0] == '.' || s[0] == p[0]) {
                return isMatch(s.substr(1), p) || isMatch(s, p.substr(2));
            } else return isMatch(s, p.substr(2));
        } else {
            if (p[0] == '.' || s[0] == p[0]) {
                return isMatch(s.substr(1), p.substr(1));
            } else return false;
        }

    }