# lc10. Regular Expression Matching

Contents

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:

 ``````1 2 3 `````` ``````Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa". ``````

Example 2:

 ``````1 2 3 `````` ``````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:

 ``````1 2 3 `````` ``````Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)". ``````

Constraints:

• `1 <= s.length <= 20`
• `1 <= p.length <= 30`
• `s` contains only lowercase English letters.
• `p` contains only lowercase English letters, `'.'`, and `'*'`.
• It is guaranteed for each appearance of the character `'*'`, there will be a previous valid character to match.
###### 解题思路 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 `````` ``````class Solution: def isMatch(self, s, p): m = len(s) + 1 n = len(p) + 1 dp = [[False for _ in range(n)] for _ in range(m)] dp = True for j in range(2, n): if p[j-1] == '*': dp[j] = dp[j - 2] for r in range(1, m): i = r - 1 for c in range(1, n): j = c - 1 if s[i] == p[j] or p[j] == '.': dp[r][c] = dp[r - 1][c - 1] elif p[j] == '*': if p[j - 1] == s[i] or p[j - 1] == '.': dp[r][c] = dp[r - 1][c] or dp[r][c - 2] else: dp[r][c] = dp[r][c - 2] else: dp[r][c] = False return dp[m - 1][n - 1] ``````