[LeetCode]10. Regular Expression Matching

原题链接：https://leetcode.com/problems/regular-expression-matching/description/

实现正则表达式中‘.’和 ‘*’的功能；

正则表达式‘.’代表一个任意字符，‘*’代表该符号前字符任意个数，所以‘*’之前肯定是要有一个字符的。

我的实现（递归+分情况讨论）：

class Solution {
public:
    bool isMatch(string s, string p) {
        return isMatch(s, p, 0, 0);
    }
    
    bool isMatch(string s, string p, int i, int j) {
        if (j == p.length()) {
            return i == s.length();
        } else if (j == p.length() - 1) {
            return (p[j] == '.' || p[j] == s[i]) && isMatch(s, p, i+1, j+1);
        } else if (i < s.length() && j < p.length() - 1 && p[j+1] != '*') {
            return (p[j] == '.' || p[j] == s[i]) && isMatch(s, p, i+1, j+1);
        } else if (i < s.length() && j < p.length() - 1 && p[j+1] == '*') {
            while ((p[j] == '.' || s[i] == p[j]) && i < s.length()) {
                if (isMatch(s, p, i, j+2))
                    return true;
                i++;
            }
            
            return isMatch(s, p, i, j+2);
        } else {
            if (j < p.length() - 1 && p[j+1] == '*')
                return isMatch(s, p, i, j+2);
            else
                return false;
        }
    }
};

总结：正则表达式，递归，速度很慢有时间看看别人的实现。

[LeetCode]10. Regular Expression Matching

相关推荐