正则表达式匹配 困难🌟🌟🌟
问题描述
原文链接：10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
1 <= s.length <= 201 <= p.length <= 20s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
代码实现
Java
class Solution {
/*
1、dp[i][j]：表示字符串长度为 i 的字符s和长度为 j 字符p是否匹配。
s = "aaaa"
p = "abca*"
2、求关系式 dp[i][j]
在匹配的时候，肯定需要关注 s[i] 和 p[j]
(1)、如果 p[j] 是普通字符:s[i] == p[j]=>dp[i][j] = dp[i-1][j-1]
s[i] != p[j]=>dp[i][j] = false.
(2)、如果 p[j] = '.' =>dp[i][j] = dp[i-1][j-1]
(3)、如果 p[j] = '*'，那么我们需要关注p[j-1]
a.如果 P[j-1] != s[i] => dp[i][j] = dp[i][j-2]
b.如果 p[j-1] == s[i]：
1).匹配0个=》dp[i][j] = dp[i][j-2]
2).匹配1个=〉dp[i][j] = dp[i-1][j-2]
3).匹配多个,相当于抵消了s[i]=》dp[i][j] = dp[i-1][j]。
dp[i][j] = dp[i][j-2] or dp[i-1][j-2] or dp[i-1][j]
3、求初始值
dp[0][j] = dp[0][j] = dp[0][j-2]。
dp[0][0] = true.
return dp[n][m]
*/
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n+1][m+1];
// 初始值
dp[0][0] = true;
for(int j = 2; j <= m; j++){
if(p.charAt(j - 1) == '*'){
dp[0][j] = dp[0][j-2];
}
}
// 进入正题
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
// 如果不是 *
if(p.charAt(j-1) != '*'){
if(p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i-1)){
dp[i][j] = dp[i-1][j-1];
}
}else{
// 如果是 *
// 匹配0个
if(p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != '.'){
dp[i][j] = dp[i][j-2];
}else{
dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];
}
}
}
}
return dp[n][m];
}
}
Python
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
n = len(s)
m = len(p)
dp = [[False] * (m+1) for _ in range(n+1)]
# 初始值
dp[0][0] = True
for j in range(2, m+1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j-2]
# 进入正题
for i in range(1, n + 1):
for j in range(1, m + 1):
# 如果不是 *
if p[j-1] != '*':
if p[j-1] == '.' or p[j-1] == s[i-1]:
dp[i][j] = dp[i-1][j-1]
else:
# 如果是 *
# 匹配0个
if p[j-2] != s[i-1] and p[j-2] != '.':
dp[i][j] = dp[i][j-2]
else:
dp[i][j] = dp[i][j-2] or dp[i-1][j-2] or dp[i-1][j]
return dp[n][m]
C++
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.length();
int m = p.length();
vector<vector<bool>> dp(n+1, vector<bool>(m+1));
// 初始值
dp[0][0] = true;
for(int j = 2; j <= m; j++){
if(p[j - 1] == '*'){
dp[0][j] = dp[0][j-2];
}
}
// 进入正题
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
// 如果不是 *
if(p[j-1] != '*'){
if(p[j-1] == '.' || p[j-1] == s[i-1]){
dp[i][j] = dp[i-1][j-1];
}
}else{
// 如果是 *
// 匹配0个
if(p[j-2] != s[i-1] && p[j-2] != '.'){
dp[i][j] = dp[i][j-2];
}else{
dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];
}
}
}
}
return dp[n][m];
}
};
Go
func isMatch(s string, p string) bool {
n := len(s)
m := len(p)
dp := make([][]bool, n+1)
for i := range dp {
dp[i] = make([]bool, m+1)
}
// 初始值
dp[0][0] = true
for j := 2; j <= m; j++ {
if p[j-1] == '*' {
dp[0][j] = dp[0][j-2]
}
}
// 进入正题
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
// 如果不是 *
if p[j-1] != '*' {
if p[j-1] == '.' || p[j-1] == s[i-1] {
dp[i][j] = dp[i-1][j-1]
}
} else {
// 如果是 *
// 匹配0个
if p[j-2] != s[i-1] && p[j-2] != '.' {
dp[i][j] = dp[i][j-2]
} else {
dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j]
}
}
}
}
return dp[n][m]
}