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 <= 30s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 如果从整个字符串去考虑，会有些迷茫。
- 用动态规划的思想，可以从0个字符到1个字符，再到2个字符，整个字符串的匹配情况依赖于去掉最后一个字符的匹配情况，以此类推。
题解
rust
impl Solution {
pub fn is_match(s: String, p: String) -> bool {
let s = s.as_bytes();
let p = p.as_bytes();
let match_c = |i, j| -> bool {
i != 0 && (p[j - 1] == '.' as u8 || s[i - 1] == p[j - 1])
};
let mut dp = vec![vec![false; p.len() + 1]; s.len() + 1];
dp[0][0] = true;
(0..=s.len()).for_each(|i| {
(1..=p.len()).for_each(|j| {
dp[i][j] = if p[j - 1] == '*' as u8 {
match_c(i, j - 1) && dp[i - 1][j] || dp[i][j - 2]
} else {
match_c(i, j) && dp[i - 1][j - 1]
};
})
});
dp[s.len()][p.len()]
}
}
go
func isMatch(s string, p string) bool {
m, n := len(s), len(p)
matches := func(i, j int) bool {
if i == 0 {
return false
}
if p[j-1] == '.' {
return true
}
return s[i-1] == p[j-1]
}
f := make([][]bool, m+1)
for i := 0; i < len(f); i++ {
f[i] = make([]bool, n+1)
}
f[0][0] = true
for i := 0; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
f[i][j] = f[i][j] || f[i][j-2]
if matches(i, j-1) {
f[i][j] = f[i][j] || f[i-1][j]
}
} else if matches(i, j) {
f[i][j] = f[i][j] || f[i-1][j-1]
}
}
}
return f[m][n]
}
c++
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
auto matches = [&](int i, int j) {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
}
return s[i - 1] == p[j - 1];
};
vector<vector<int>> f(m + 1, vector<int>(n + 1));
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
f[i][j] |= f[i][j - 2];
if (matches(i, j - 1)) {
f[i][j] |= f[i - 1][j];
}
} else {
if (matches(i, j)) {
f[i][j] |= f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
};
java
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
char pc = p.charAt(j - 1);
if (pc == '*') {
dp[i][j] = dp[i][j - 2]; // *匹配0次
if (i > 0 && !dp[i][j]) {
char prePc = p.charAt(j - 2);
if (prePc == '.'
|| s.charAt(i - 1) == prePc) {
dp[i][j] = dp[i - 1][j]; // *匹配1次或多次
}
}
} else if (i > 0 && (pc == '.' || s.charAt(i - 1) == pc)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
typescript
function isMatch(s: string, p: string): boolean {
let m = s.length;
let n = p.length;
const matches = function (i: number, j: number): boolean {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
}
return s[i - 1] == p[j - 1];
};
let f = Array.from({
length: m + 1 }, () => Array.from({
length: n + 1 }, () => false));
f[0][0] = true;
for (let i = 0; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
f[i][j] = f[i][j] || f[i][j - 2];
if (matches(i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
} else if (matches(i, j)) {
f[i][j] = f[i][j] || f[i - 1][j - 1];
}
}
}
return f[m][n];
};
python
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
def matches(i: int, j: int) -> bool:
if i == 0:
return False
if p[j - 1] == '.':
return True
return s[i - 1] == p[j - 1]
f = [[False] * (n + 1) for _ in range(m + 1)]
f[0][0] = True
for i in range(m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
f[i][j] |= f[i][j - 2]
if matches(i, j - 1):
f[i][j] |= f[i - 1][j]
else:
if matches(i, j):
f[i][j] |= f[i - 1][j - 1]
return f[m][n]
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
