「LeetCode」Wildcard Matching 題解

Implement wildcard pattern matching with support for "?" and "*".

"?" Matches any single character."*" Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:bool isMatch(const char *s, const char *p)

Some examples:isMatch("aa","a") ? falseisMatch("aa","aa") ? trueisMatch("aaa","aa") ? falseisMatch("aa", "*") ? trueisMatch("aa", "a*") ? trueisMatch("ab", "?*") ? trueisMatch("aab", "c*a*b") ? false

這裡的難點在於如何處理*，因為這個星號可以代表0到多個字元，而且有可能會遇到遞歸一開始匹配正確後面不正確，但實際上應該從後面開始匹配。

class Solution(object):
# p為匹配模式，s為字元串
def recursive(self, s, p, si, pi, cur):
first = True
n_cur = cur
while si < len(s) and pi < len(p) and (s[si] == p[pi] or p[pi] == "?"): si += 1 pi += 1 if pi == len(p): return si == len(s) if p[pi] == "*": while pi < len(p) and p[pi] == "*": pi += 1 if pi >= len(p):
return True
for i in range(si, len(s)):
# 表明開始重合，從這裡再度開始遞歸
if p[pi] != s[i] and p[pi] != "?":
continue
if first:
cur += 1
first = False
# 可能存在多次重合但是還不算真正匹配的情況
if self.recursive(s, p, i, pi, cur + 1):
return True
if cur > n_cur + 1: # 正常來說n_cur = cur + 1
return False
return False
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
return self.recursive(s, p, 0, 0, 0)

這種做法超時。

DP

我們定義一個二維數組dp，橫坐標為待匹配字元串，縱坐標為模式字元串，dp[i][j]則代表到模式字元串從0到 i 對應待匹配字元串的的0到 j 是否是匹配的。舉個例子：

pattern = "a*bc"
str = "abbc"

我們可以根據前面提到的畫出整個二維數組

我們可以發現一個規律，每當遇到兩個字元不相等的時候，那麼數組的值則肯定是False，相反相等的時候肯定是True，這裡需要注意的是*，這裡則需要考慮到它當前可能匹配0個字元串或者匹配多個字元，比如上面中的a*和ab的情況，此時我們需要發現a*及a或者a和ab其中有任何一個成功匹配的，它的結果也肯定為T。

這個狀態轉義方程要怎麼推算出來呢？

如果p.charAt(i)=="*"，"*"可以選擇匹配0個字元，此時flag[i][j]=flag[i-1][j];可以選擇匹配1個字元，此時flag[i][j]=flag[i-1][j-1];……所以可以得到下面的公式：

因為flag[i][j]=flag[i-1][j]||flag[i-1][j-1]||……||flag[i-1][0]，我們可以代入上面的公式得到：

於是我們可以很簡單的寫出程序了（下面的程序的i，j和狀態轉義方程是相反的，但是原理是相同的）

class Solution(object):
# p為匹配模式，s為字元串
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if len(s) != len(p) - p.count("*"):
return False
newp = ""
i = 0
while i < len(p): newp += p[i] if p[i] == "*": while i + 1 < len(p) and p[i + 1] == "*": i += 1 i += 1 sl, pl = len(s), len(newp) dp = [[False for x in range(pl + 1)] for y in range(sl + 1)] dp[0][0] = True if pl > 0 and p[0] == "*":
dp[0][1] = True
for x in range(1, sl + 1):
for y in range(1, pl + 1):
if newp[y - 1] != "*":
dp[x][y] = dp[x - 1][y - 1] and (s[x - 1] == newp[y - 1] or newp[y - 1] == "?")
else:
dp[x][y] = dp[x - 1][y] or dp[x][y - 1]
return dp[sl][pl]

同樣的原理，我們還可以把它縮減成一維數組，你可以把它想像成在二維數組中計算每一行的數據，如果遇到*則更新當前行的數據；為什麼可以這麼做呢？我們可以根據前面提到的公式發現，其中當前的數據依賴於j的變化，也就是待匹配字元串的值，我們還需要在外面寫個模式串的循環，其實和二維數組的做法的時間複雜度是一樣的，但是縮減了空間，但是並不是所有的都可以這麼做，這個取決於你的依賴項是什麼。總而言之，其原理還是一樣的，只是想辦法讓它們的數據能夠共存到一維數組中。

class Solution:
# @return a boolean
def isMatch(self, s, p):
length = len(s)
if len(p) - p.count("*") > length:
return False
dp = [True] + [False]*length
for i in p:
if i != "*":
# 因為依賴項是前面的值，所以不能從前面往後面掃，得從後往前計算
for n in reversed(range(length)):
dp[n+1] = dp[n] and (i == s[n] or i == "?")
else:
# 更新當前行的數據
for n in range(1, length+1):
dp[n] = dp[n-1] or dp[n]
dp[0] = dp[0] and i == "*"
return dp[-1]

貪心演算法

1. 如果當前相等或者模式串中字元為?，則移動相互的下標即可；
2. 如果當前模式串字元為*，分別紀錄lastmatch、laststar，並且移動模式串下標，但是不移動待匹配字元串下標，因為可能存在匹配0個字元串的情況；
3. 如果當前相互對應的字元不再相等且不為*，如果前面有*號，說明之前的匹配失敗了，模式字元串下標回到之前紀錄laststar的後一位，不再移動，專門用來給待匹配字元串字元來匹配，這段時間內，si會不斷的向前移動，直到匹配到相互的值相等才移動模式字元串的下標；
4. 如果前面的情況都不符合，則肯定為False；

看看我的抽象派畫風。

class Solution(object):
# p為匹配模式，s為字元串
def isMatch(self, s, p):
si, pi = 0, 0
lastmatch, laststar = -1, -1
sl, pl = len(s), len(p)
if pl - p.count("*") > sl:
return False
# 注意條件順序
while si < sl: if pi < pl and (s[si] == p[pi] or p[pi] == "?"): pi += 1 si += 1 elif pi < pl and p[pi] == "*": lastmatch, laststar = si, pi # 之所以不更新lastmatch是因為考慮到*只匹配0個字元串 pi += 1 # 再次進到這個判斷，說明當前下標對應的值不相等 elif laststar != -1: pi = laststar + 1 # pi當前不是*，並且回到上一次星的後面，專門用來給si匹配 lastmatch += 1 # 必須更新lastmatch，因為之前已經不想等，如果在回到開始的狀態就會陷入死循環 si = lastmatch else: return False # 可能存在p的末尾都是*的情況 while pi < len(p) and p[pi] == "*": pi += 1 # 最後匹配成功模式字元串的下標必然為其長度，表示已經匹配完成 return pi == pl

tips：不要小看保存你的長度值，如果你頻繁的用到的話，最好保存下來，比如在這裡，我保存下來以後可以讓我提升%10的beat submissions！

一樣的原理，但是使用了遞歸的方式來做

class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
seen = {}
wild_single, wild_multi = "?", "*"
# seen has the pattern - source tuple as key, and bool result as success
source, pattern = s, p
def is_match(sindex, pindex):
key = (sindex, pindex)
if key in seen:
return seen[key]
result = True
# if there"s no string, and pattern is not only * then fail
if sindex >= len(source):
for wildindex in xrange(pindex, len(pattern)):
if pattern[wildindex] != wild_multi:
result = False
break
# there"s a string, but no pattern
elif pindex >= len(pattern):
result = False
# if next pattern is multi though, that"s something
elif pattern[pindex] == wild_multi:
# for zero, simply check sindex, pindex + 1
result = is_match(sindex, pindex + 1) # just for easier debug
# if zero, than it"s a match
# otherwise we need to check multi
# for that, if char is not a wild, then it has to match the source,
result = result or is_match(sindex + 1, pindex)
else:
# either a regular char, or wild_single
result = (( pattern[pindex] == wild_single or pattern[pindex] == source[sindex]) and
is_match(sindex + 1, pindex + 1))
seen[key] = result
return result
if (len(p) - p.count(wild_multi) > len(s)):
return False
return is_match(0, 0)

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！