> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/string-match/regular-expression-matching.md).

# 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

```cpp
/*
 * @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).