LeetCode 44. 通配符匹配
一道简化版的正则表达式匹配题。
题目描述
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
- '?' Matches any single character.
- '*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = ""
Output: true
Explanation: '' matches any sequence.
Example 3:
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input: s = "adceb", p = "ab"
Output: true
Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce".
Example 5:
Input: s = "acdcb", p = "a*c?b"
Output: false
Constraints:
- 0 <= s.length, p.length <= 2000
- s contains only lowercase English letters.
- p contains only lowercase English letters, '?' or '*'.
解题思路
这道题是对 LeetCode 10. 正则表达式匹配 的简化，区别在于：
- 使用 '?' 代替正则表达式中的 '.'
- 使用单个字符 '' 来匹配0个或任意多个字符，正则表达式是用 "a" / ".*" 两个字符才能匹配0个或多个字符。
这就简化了题目，遇到 '' 的时候不用向前看一个字符了，可以直接原地匹配0个字符、1个字符、多个字符。本题的考点就在于 '' 匹配2个及以上字符的状态转移方程。
先做这道题，在做正则表达式匹配的题，可能会更顺利一些。
参考代码
/*
* @lc app=leetcode id=44 lang=cpp
*
* [44] Wildcard Matching
*/
// @lc code=start
class Solution {
public:
bool isMatch(string s, string p) {
if (!s.empty() && p.empty()) return false;
size_t ns = s.size(), np = p.size();
vector<vector<bool>> dp(ns+1, vector<bool>(np+1));
dp[0][0] = true;
for (int i=1; i<=ns; i++) {
dp[i][0] =false;
}
for (int j=1; j<=np; j++) {
dp[0][j] = dp[0][j-1] && (p[j-1] == '*');
}
for (int i=1; i<=ns; i++) {
for (int j=1; j<=np; j++) {
if (s[i-1] == p[j-1] || p[j-1] == '?') {
dp[i][j] = dp[i-1][j-1];
} else if (p[j-1] == '*') {
// match 0, 1, or n char
dp[i][j] = dp[i][j-1] || dp[i-1][j-1] || dp[i-1][j];
} else {
dp[i][j] = false;
}
}
}
return dp[ns][np];
} // AC
};
// @lc code=end