原题链接: Leetcode 10. 正则表达式匹配
题目描述
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
'.'
匹配任意单个字符
'*'
匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
说明:
s
可能为空,且只包含从 a-z
的小写字母。
p
可能为空,且只包含从 a-z
的小写字母,以及字符 .
和 *
。
解题思路
二维dp
- 状态表示:
dp[i][j]
: 字符串s前i个字母
能否被p的前j个字母
表示
- 状态计算:
- 枚举
p[j]
的所有可能的字母
s[i] = p[j]
或 p[j] = '.'
dp[i][j] = dp[i - 1][j - 1]
p[j] = '*'
- 不使用
*
- 需要s[1~i]与p[1~j]匹配上:
dp[i][j] = dp[i][j - 2]
- 使用
*
- 需要
s[i] = p[j - 1]
或者p[j - 1] = .
才可以用*
- 需要
s[1 ~ i-1]
与p[1~j]
匹配上
dp[i][j] = dp[i - 1][j]
代码:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| class Solution { public: bool isMatch(string s, string p) { int m, n; n = s.size(), m = p.size(); s = ' ' + s; p = ' ' + p; vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false)); dp[0][0] = true;
for(int i = 2; i <= m; i ++) { if(p[i] == '*') dp[0][i] = dp[0][i - 2]; }
for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j++) { if(p[j] == '.' || s[i] == p[j]) dp[i][j] = dp[i - 1][j - 1]; else { if(p[j] == '*') { dp[i][j] = dp[i][j - 2]; if(p[j - 1] == '.' || s[i] == p[j - 1]) dp[i][j] = dp[i][j] | dp[i - 1][j]; } } } return dp[n][m]; } };
|
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution: def isMatch(self, s: str, p: str) -> bool: s, p = ' ' + s, ' ' + p n, m = len(s), len(p) dp = [[0] * m for _ in range(n)]
dp[0][0] = 1 for i in range(2, m): if p[i] == '*': dp[0][i] = dp[0][i - 2]
for i in range(1, n): for j in range(1, m): if (s[i] == p[j] or p[j] == '.'): dp[i][j] = dp[i - 1][j - 1] else: if p[j] == '*': dp[i][j] = dp[i][j - 2] if (p[j - 1] == '.' or s[i] == p[j - 1]): dp[i][j] |= dp[i - 1][j] return dp[n - 1][m - 1] == 1
|