2024每日刷题（112）
Leetcode—44. 通配符匹配
算法思想
实现代码
class Solution {
public:
bool isMatch(string s, string p) {
auto isMatchchar = [&](int i, int j)->bool {
return p[j] == '?' || s[i] == p[j];
};
int m = s.size();
int n = p.size();
// dp[i][j] := true if s[0..i) matches p[0..j)
// 即true if s[0...i-1] matches p[0...j-1]
vector<vector<bool>> dp(m + 1, vector<bool>(n+1));
dp[0][0] = true;
for(int j = 0; j < n; j++) {
if(p[j] == '*') {
dp[0][j + 1] = dp[0][j];
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(p[j] == '*') {
// s[0...i]和p[0...j-1]的匹配程度
// 如果上面为true, 即'*'匹配空字符串
const bool matchEmpty = dp[i+1][j];
// s[0...i-1]和p[0...j]的匹配程度
// 如果上面为true, 即'*'匹配s[i]
const bool matchSome = dp[i][j+1];
dp[i+1][j+1] = matchEmpty || matchSome;
} else {
if(isMatchchar(i, j)) {
dp[i+1][j+1] = dp[i][j];
}
}
}
}
return dp[m][n];
}
};
运行结果
之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！
