题目

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

’.’ Matches any single character.​​​​ ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Example 1:

Input: s = “aa”, p = “a” Output: false Explanation: “a” does not match the entire string “aa”. Example 2:

Input: s = “aa”, p = “a*” Output: true Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”. Example 3:

Input: s = “ab”, p = “.*” Output: true Explanation: “.” means “zero or more () of any character (.)”.

答案

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;

        // 初始化空字符串与模式串的匹配（处理 a* 等可以匹配空的情况）
        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] != '*') {
                    // 普通字符或 '.'，必须当前字符匹配且前面子串匹配
                    if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    // '*' 的情况：匹配0次 或 多次
                    dp[i][j] = dp[i][j - 2]; // 匹配0次
                    if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j]; // 匹配多次
                    }
                }
            }
        }
        return dp[m][n];
    }
};

思路

• 理解题目
  • 题目来自于正则表达式的一种算法，其中.可以替代任意一个字符，*表示由*前一个字符重复0次或多次。
  • 例如：
    • aa与a匹配失败，因为a只匹配一个字符，而aa匹配两个字符。
    • aa与a*匹配成功，因为a*表示由a重复0次或多次，所以aa可以匹配。
• 基于*可以匹配无数个字符的情况，我们认为这是符合动态规划的形状的，尝试利用动态规划求解。
  • 动态规划的状态转移方程：
    • dp[i][j]表示s的前i个字符与p的前j个字符是否匹配。
  • 对于.和正常的字符，我们可以直接判断是否相等，并不会带来复杂的判断。即dp[i][j]=(s[i]==p[j]||p[j]=='.')&&(((j>0)&&(i>0)&&dp[i-1][j-1])||(j==0&&i==0))

  • 对于*，我们需要考虑多种情况。

    • 首先我们要考虑空串的情况。这一情况在marked数组中有所体现。对于?*?*?*···?*这种情况。每个*对应的位置都是可以接受空串的。其中?代表任意字符。
    • 考虑到?*可以匹配空串，因此当p[j]为*时，dp[i][j]=dp[i][j-2]。
    • 在不匹配空串的情况下，只能匹配s[i]···s[0]当中第一个与p[j-1]不同的字符，如果p[j-1]为.，那就可以一直匹配下去。
  • 观察到marked带来的不变，应当将它整合到dp数组当中。这一过程不在讨论，交由读者自行解决。
• 最后，我们返回dp数组的最后一个元素，即dp[ssize-1][psize-1]，即可判断是否匹配成功。