题目

题解

1. 普通递归

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();//若p为空，则s为空返回false。否则返回true
        //若s不为空且当前字符普配（s当前字符等于p当前字符，或者s当前字符等于.)，nMatch为true
        bool nMatch = !s.empty() && (p[0] == s[0] || p[0] == '.');
        //讨论p为*的情况，若下一位为*
        if(p[1] == '*'){
            //则递归两种情况，
            //1. 跳过p中的该字符与*号，即有0个该字符
            //2. 与本字符匹配（nMatch），递归下一个s而p不变（*前的字符有可能多个）
            return isMatch(s, p.substr(2)) ||
                    (nMatch && isMatch(s.substr(1), p));
        }else{//若下一位不为*，挨个匹配递归
            return nMatch && isMatch(s.substr(1), p.substr(1));
        }
    }
};

2. 记忆递归

自己写了半天老是溢出，这里是来自mecury的代码，用一个二维数组存储已经递归过的位置

class Solution {
public:
    //记忆表
    vector<vector<int>>memo;
    bool isMatch(string s, string p) {
        // 大小+1的目的是因为memo有边界限制，在递归出口是只判断了pi，但没有限制si
        memo = vector<vector<int>>(s.size() + 1, vector<int>(p.size() + 1, -1));
        return helper(0, 0, s, p);
    }
    bool helper(int si, int pi, string s, string p) {
        //递归出口
        //当si==s.size() 且 pi < p.size()时 可能p中还有“*”字符 可以令前面的字符出现0次以匹配s
        if(pi == p.size()) {
            return si == s.size();
        }
        //如果判断过了直接返回存储的结果
        if(memo[si][pi] != -1) { 
            return memo[si][pi]; 
        } 
        bool res = false; //整个结果是否匹配
        bool cur_match = false; //当前字符是否匹配
        if(si < s.size()) {
            if(s[si] == p[pi] || p[pi] == '.') {
                cur_match = true;
            }
        }
        //判断下一个字符是否'*'
        if((pi + 1) < p.size() && p[pi + 1] == '*') {
            // 考虑只需两种情况：
            // 情况1：当前字符出现0次：跳过pattern中的当前字符和下一个"*"==>helper(si, pi + 2, s, p)
            // 情况2：当前字符出现1次：当前是否匹配 && 将字符s向后移动一位是否匹配==>cur_match && helper(si + 1, pi, s, p)
            res = helper(si, pi + 2, s, p) || (cur_match && helper(si + 1, pi, s, p));
        } else {
            res = cur_match && helper(si + 1, pi + 1, s, p); //下一个不是"*"正常向后匹配就好
        }
        memo[si][pi] = res;
        return res;
    }
};

3. 动态规划

这题已经把我绕晕了，先放一放。动态规划的方法来自(https://leetcode.com/problems/regular-expression-matching/discuss/5684/c-on-space-dp)
We define dp[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. The state equations will be:

dp[i][j] = dp[i - 1][j - 1], if p[j - 1] != ‘*’ && (s[i - 1] == p[j - 1] || p[j - 1] == ‘.');
dp[i][j] = dp[i][j - 2], if p[j - 1] == ‘*’ and the pattern repeats for 0 time;
dp[i][j] = dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == ‘.'), if p[j - 1] == ‘*’ and the pattern repeats for at least 1 time.

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j > 1 && p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                } else {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return dp[m][n];
    }
};

4. 正则匹配

class Solution {
public:
    bool isMatch(string s, string p) {
        return regex_match(s, regex(p));
    }
};