題目描述
給定一個輸入字串 s 和一個Pattern p，其中：
s是輸入字串，只包含小寫字母。p是匹配模式字串，可能包含以下特殊字元：- ? 可以匹配任何單個字元。
- * 可以匹配任意長度（包括 0）的一段字元。
* 和 ?的Wildcard Pattern Matching的函式。範例 1：
輸入: s = "aa", p = "a"
輸出: false
解釋: "a" 只能匹配一個 'a'，而非兩個。
範例 2：
輸入: s = "aa", p = "*"
輸出: true
解釋: '*' 可以匹配任意字元序列。
範例 3：
輸入: s = "cb", p = "?a"
輸出: false
解釋: '?' 可以匹配 'c'，但 'a' 無法匹配 'b'。
解題思路
這題類似於正則表達式匹配，但難度更高，因為我們需要處理 * 和 ? 的匹配規則。根據問題特性，有以下幾種解法。
解法一：動態規劃
思路
- 使用一個二維 DP 陣列
dp，其中dp[i][j]表示s的前i個字元與p的前j個字元是否匹配。 - 初始化：
- dp[0][0] = True：空字串和空模式匹配。
- dp[0][j] = True，當 p[1..j] 全是 * 時。
- 其他情況初始化為 False。
- 遞推公式：
- 如果 p[j-1] == s[i-1] 或 p[j-1] == '?'，則 dp[i][j] = dp[i-1][j-1]。
- 如果 p[j-1] == '*'，則 dp[i][j] = dp[i-1][j] or dp[i][j-1]：dp[i-1][j] 表示 * 匹配多個字元。dp[i][j-1] 表示 * 匹配 0 個字元。
- 返回結果：
dp[len(s)][len(p)]。
程式碼
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
# 初始化 DP 陣列
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# 初始化 p 開頭為 '*' 的情況
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
# 填充 DP 陣列
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == s[i - 1] or p[j - 1] == '?':
dp[i][j] = dp[i - 1][j - 1]
elif p[j - 1] == '*':
dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
return dp[m][n]
時間與空間複雜度
- 時間複雜度：O(m*n)，其中 m 是
s的長度，n 是p的長度。 - 空間複雜度：O(m*n)，用於存儲 DP 陣列。
解法二：雙指針法
思路
- 使用兩個指針：
- i 遍歷 s。
- j 遍歷 p。
- 記錄最近一次
*出現的位置，以及當前匹配到的字串位置。 - 當匹配失敗時，回溯到上一個
*的位置，並嘗試擴展匹配的長度。 - 如果模式中所有的
*都被嘗試過，則匹配失敗。
程式碼
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
i = j = 0 # 指向 s 和 p 的指針
star_index = -1
match_index = 0
while i < m:
# 當字元匹配或遇到 '?' 時
if j < n and (p[j] == s[i] or p[j] == '?'):
i += 1
j += 1
# 遇到 '*'，記錄星號的位置，並假設它匹配 0 個字元
elif j < n and p[j] == '*':
star_index = j
match_index = i
j += 1
# 匹配失敗但之前有星號，回溯到星號
elif star_index != -1:
j = star_index + 1
match_index += 1
i = match_index
else:
return False
# 檢查剩餘的模式是否全是 '*'
while j < n and p[j] == '*':
j += 1
return j == n
時間與空間複雜度
- 時間複雜度：O(m+n)，其中 m 是
s的長度，n 是p的長度。 - 空間複雜度：O(1)，只使用常數空間。
結論
- 如果需要簡潔高效的解法，雙指針法 是較好的選擇，適合處理大規模字串。
- 如果對於邊界條件需要嚴格檢查，則使用 動態規劃，較為直觀且容易調試。
- 這題的核心在於處理
*和?的靈活匹配，熟練掌握這些技巧後，類似題型的解法會更容易。
希望這篇解題教學對大家有幫助！
