LeetCode 10——正则表达式匹配

1. 题目

2. 解答

在回溯算法中我们介绍了一种递归的思路来求解这个问题。

此外，这个问题也可以用动态规划的思路来解决。我们定义状态 (P[i][j]) 为子串 (s[0, i)) 和 (p[0, j)) 是否匹配，能匹配为真，反之为假，然后状态转移方程则可以分为以下三种情况：

1. 如果 p[j-1] != ‘*’ && (s[i-1] == p[j-1] || p[j-1] == ‘.’) ，说明当前两个字符可以匹配且没有遇到 ('*')，那么此时 P[i][j] = P[i-1][j-1]，也即若 (s[0, i-1)) 和 (p[0, j-1)) 匹配，则 (s[0, i)) 和 (p[0, j)) 也能匹配；
1. 如果 p[j-1] == ‘*’ ，说明当前字符为 ('*')，并且我们用其匹配零个字符，那么 P[i][j] = P[i][j-2]，也即若 (s[0, i)) 和 (p[0, j-2)) 匹配，则跳过 (p[j-2],p[j-1]) 两个元素后 (s[0, i)) 和 (p[0, j)) 也能匹配；
1. 如果 p[j-1] == ‘*’ ，说明当前字符为 ('*')，并且我们用其匹配至少一个字符，而且还需满足 s[i-1] == p[j-2] || p[j-2] == ‘.’，那么 P[i][j] = P[i-1][j]，也即若 (s[0, i-1)) 和 (p[0, j)) 匹配，那么我们用这个 ('*') 来匹配 (s[i-1]) 后， (s[0, i)) 和 (p[0, j)) 也就能匹配。至少一次是说这里 ('*') 已经被用了一次，而前面 (s[0, i-1)) 和 (p[0, j)) 的匹配也有可能会用到。

其中 2 和 3 只需满足一个即可匹配，代码如下。

class Solution {
public:

    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size(); 
        vector<bool> temp(n+1, false);
        vector<vector<bool> > dp(m+1, temp);
        dp[0][0] = true;

        for (int j = 1; j <= n; j++)
            if (p[j - 1] == '*')
                dp[0][j] = dp[0][j-2];

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (p[j - 1] == '*')
                {
                    bool repeat_zero = false;
                    bool repear_one_more = false;
                    repeat_zero = dp[i][j - 2];
                    if (s[i - 1] == p[j - 2] || p[j - 2] == '.')
                         repear_one_more = dp[i - 1][j];
                    dp[i][j] = repeat_zero || repear_one_more;
                }
                    
                else 
                {
                    if (s[i - 1] == p[j - 1] || p[j - 1] == '.')
                        dp[i][j] = dp[i-1][j-1];
                }      
            }
        }
        return dp[m][n];
    }
};

获取更多精彩，请关注「seniusen」!