Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/description/

Implement regular expression matching with support for'.'and'*'.

'*' Matches zero or more of the preceding element.

Thoughts

字符串匹配问题首先想到DP。相等或'.'时没什么特别的。星号表示可以前面的字符可以出现0个或以上, 先检查0个时能否match，即f[i][j-2]； 再检查0个以上时看star是否 match了所有i前面的与s[i]相同的字符，即f[i-1][j]，最后让s[i]再match个*。

Code

/*
 * @lc app=leetcode id=10 lang=cpp
 *
 * [10] Regular Expression Matching
 *
 * https://leetcode.com/problems/regular-expression-matching/description/
 *
 * algorithms
 * Hard (25.60%)
 * Likes:    2994
 * Dislikes: 564
 * Total Accepted:    336.7K
 * Total Submissions: 1.3M
 * Testcase Example:  '"aa"\n"a"'
 *
 * Given an input string (s) and a pattern (p), implement regular expression
 * matching with support for '.' and '*'.
 * 
 * 
 * '.' Matches any single character.
 * '*' Matches zero or more of the preceding element.
 * 
 * 
 * The matching should cover the entire input string (not partial).
 * 
 * Note:
 * 
 * 
 * s could be empty and contains only lowercase letters a-z.
 * p could be empty and contains only lowercase letters a-z, and characters
 * like . or *.
 * 
 * 
 * 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 (.)".
 * 
 * 
 * Example 4:
 * 
 * 
 * Input:
 * s = "aab"
 * p = "c*a*b"
 * Output: true
 * Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore,
 * it matches "aab".
 * 
 * 
 * Example 5:
 * 
 * 
 * Input:
 * s = "mississippi"
 * p = "mis*is*p*."
 * Output: false
 * 
 * 
 */
class Solution {
public:
    bool isMatch(string s, string p) {
        const int M = s.size(), N = p.size();
        vector<vector<bool>> dp(M + 1, vector<bool>(N + 1));
        dp[0][0] = true;
        for (int j = 2; 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) {
                const char a = s[i - 1], b = p[j - 1];
                if (b == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (!dp[i][j] && (p[j - 2] == '.' || p[j - 2] == a)) dp[i][j] = dp[i - 1][j];
                } else if (dp[i - 1][j - 1] && (b == '.' || a == b)) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[M][N];
    }
};

Analysis

Errors: 1. 初始化时没考虑星号. 星号前的元素可以一次也不出现. 2. 当星号时, 应f[i -1][j]而不是f[i-1][j-1]. 比如s = aaa, p = a*, 当i = 2, j = 1时, f[i][j] = false. 导致当j = 2时也为false.

时间复杂度O(mn), 空间O(mn).