44. 通配符匹配 - 力扣（LeetCode）

輸入：s = "aa", p = "a"
輸出：false
解釋："a" 無法匹配 "aa" 整個字符串。

輸入：s = "aa", p = "*"
輸出：true
解釋：'*' 可以匹配任意字符串。

輸入：s = "cb", p = "?a"
輸出：false
解釋：'?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b'。

題解

題目描述：給你兩個字符串s文本字符串和p模式字符串，其中p包含兩種類型的通配符：

• *：可以匹配任意字符序列（包括空序列）
• ?：可以匹配任意單個字符

題目要求你檢查s和p是否匹配。

Example 1:

• s = "adceb"
• p = "*a*b"
• Output: true
• Explanation: The first * can match an empty sequence, and the second * matches “dce”.

Example 2:

• s = "acdcb"
• p = "a*c?b"
• Output: false
• Explanation: There is no way to match s with p, as the character before the last in s is ‘c’ but ‘b’ in p.

這個題用貪心的思路該如何去想呢，在每一步匹配中，我們可以對如何匹配字符串做出局部最優選擇，如*,可以表示任何字符序列，包括空序列，可以在匹配字符串的過程中及時調整匹配。

• 對于?：由于?只匹配一個字符，即自動選擇s的當前字符與p中的?匹配。
• 對于*：因為他可以匹配任意字符序列，所以按照貪心的思路，首先用空序列匹配*，然后，如果需要，根據模式和字符串其余部分擴展或縮小匹配的字符數量。

貪心算法的實現思路

1. 兩個指針+回溯：首先定義兩個指針，分別是s（sIdx）和p（pIdx），進行模式匹配，如果出現不匹配，則回溯到p中*的最后一個位置（如果有），并嘗試不同的匹配。
2. ?通配符處理：在迭代中，如果 s 和 p 中的當前字符匹配，或者 p[pIdx] 是 ? ，只需將兩個指針向前移動。
3. 處理*通配符：如果p是*，需要分別標記*在p中的位置（用starIdx）,和在s中的對應位置(sTmpIdx表示)。表示*匹配s中的空字符的起點。如果稍后出現不匹配，則回溯到starIdx并增加sTmpIdx，表示*現在應該在s中多匹配一個字符。將pIdx重置為starIdx+1，將 sIdx 重置為 sTmpIdx ，繼續匹配。
4. 最后檢查：遍歷 s 后，確保 p 中所有剩余的字符都是 * 。如果是，它們可以匹配空序列，因此，模式匹配字符串。

具體示例：

Consider ：s = "adceb" and p = "*a*b"

Initial Setup

• s = "adceb"
• p = "*a*b"
• sIdx = 0, pIdx = 0, starIdx = -1, sTmpIdx = -1

Iteration 1

• p[0] is *, so we update starIdx = 0 and sTmpIdx = 0.
• Increment pIdx to 1.
• sIdx remains 0.

Iteration 2

• p[1] is 'a', but s[0] is 'a'. This is a mismatch.
• Since starIdx != -1, we use the star to match one more character.
• Increment sTmpIdx to 1. So sTmpIdx = 1.
• Update pIdx = starIdx + 1, which means pIdx = 1.
• Update sIdx = sTmpIdx, which means sIdx = 1.

Iteration 3

• Now p[1] is 'a' and s[1] is also 'a'. This is a match.
• Increment both sIdx and pIdx by 1.
• sIdx = 2, pIdx = 2.

Iteration 4

• p[2] is '*'. Update starIdx = 2 and sTmpIdx = 2.
• Increment pIdx to 3.
• sIdx remains 2.

Iteration 5

• p[3] is 'b', but s[2] is 'd'. This is a mismatch.
• Since starIdx != -1, we use the star to match one more character.
• Increment sTmpIdx to 3. So sTmpIdx = 3.
• Update pIdx = starIdx + 1, which means pIdx = 3.
• Update sIdx = sTmpIdx, which means sIdx = 3.

Iteration 6

• p[3] is 'b' and s[3] is 'c'. This is a mismatch.
• We repeat the backtracking process:
• Increment sTmpIdx to 4. So sTmpIdx = 4.
• Update pIdx = starIdx + 1, which means pIdx = 3.
• Update sIdx = sTmpIdx, which means sIdx = 4.

Iteration 7

• p[3] is 'b' and s[4] is 'b'. This is a match.
• Increment both sIdx and pIdx by 1.
• sIdx = 5, pIdx = 4.

Final Check

• sIdx is now equal to s.size(), so we exit the while loop.
• Check remaining characters in p. Since pIdx is also at the end of p, there are no more characters to check.

class Solution {
public:bool isMatch(string s, string p) {int sIdx = 0, pIdx = 0;      // Pointers for s and p.int starIdx = -1, sTmpIdx = -1;  // Indices to track the most recent '*' position in p and the corresponding position in s.while (sIdx < s.size()) {// If the characters match or pattern has '?', move both pointers.if (pIdx < p.size() && (p[pIdx] == s[sIdx] || p[pIdx] == '?')) {++sIdx;++pIdx;}// If pattern has '*', record the position and assume it matches zero characters initially.else if (pIdx < p.size() && p[pIdx] == '*') {starIdx = pIdx;sTmpIdx = sIdx;++pIdx;}// If a mismatch occurs and there was a previous '*', backtrack.// Try to match '*' with one more character in s.else if (starIdx != -1) {pIdx = starIdx + 1;sIdx = ++sTmpIdx;}// If no '*' to backtrack to, return false.else {return false;}}// Check if the remaining characters in pattern are all '*'.// They can match the empty sequence at the end of s.for (; pIdx < p.size(); ++pIdx) {if (p[pIdx] != '*') {return false;}}// If we've processed both strings completely, it's a match.return true;}
};