10-正则表达式匹配

LeetCode 10. Regular Expression Matching

LeetCode-10

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".

method

dp[i][j]：s中以s[i-1]结尾的子串与p中以p[j-1]结尾的子串是否匹配

• 如果s[i-1]==p[j-1]或者p[j-1]=='.'（可以匹配任意字符），说明可以不用看这个字符，看前面的就行，所以dp[i][j] = dp[i-1][j-1]
• 否则，再看如果p[j-1]=='*'
  • 可以往前倒2个，就不看p[j-2]的字符和p[j-1]的*，如果dp[i][j-2]为true，dp[i][j]也可以是true，让p[j-2]出现0次
  • 如果dp[i][j-2]是false，再看如果s[i-1]==p[j-2]或者p[j-2]=='.'，这样的话如果dp[i-1][j]是true，那dp[i][j]也可以是true，这样就是*让前面的字符重复了一次

第一行需要初始化，如果是*，只能往前倒2个

    ×   a   b   *
×   1   0   0   0
a   0   1   0   1(*让b重复0次)
b   0   0   1   1(*让b重复了1次)
b   0   0   0   1(*让b重复了2次)

可以这样理解，如果p[j-1]=='*'，则dp[i][j] = dp[i][j-2] || dp[i-1][j]，不过后面这个的前提是s[i-1]==p[j-2]

比如B和BA*是匹配的，现在要看BA和BA*是否匹配，因为s[i-1]=A和p[j-2]=A是匹配的，所有只要用*让前面的A再重复一次就可以了

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 j = 2; j <= n; j++) {
        if (p[j - 1] == '*') 
            dp[0][j] = dp[0][j - 2];    // 只能往前倒2个
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if (p[j - 1] == '*' && j >= 2) {// 因为要往前倒2个，保证不越界
                if (dp[i][j - 2]) dp[i][j] = true;  // 往前倒2个
                else if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
                    dp[i][j] = dp[i - 1][j];    // 也可以从上面下来
                }
            }
        }
    }
    return dp[m][n];
}