Leetcode 44：ワイルドカードマッチング（非常に詳細なソリューション!!!）
Leetcode 44 Wildcard Matching Ultra Detailed Solution
文字列（s）と文字パターン（p）を指定して、サポートを実現する'?' '*'でワイルドカードが一致します。
'?' can match any single character. '*' can match any string (including an empty string). 2本の弦 完全に一致 試合だけが成功します。
説明：
s空の場合があり、a-zのみが含まれます小文字。p空の場合があり、a-zのみが含まれます小文字と文字?*で。
例1：
Enter: s = 'aa' p = 'a' Output: false Explanation: 'a' cannot match the entire string 'aa'. 例2：
Enter: s = 'aa' p = '*' Output: true Explanation: '*' can match any string. 例3：
Enter: s = 'cb' p = '?a' Output: false Explanation: '?' can match 'c', but the second 'a' cannot match 'b'. 例4：
Enter: s = 'adceb' p = '*a*b' Output: true Explanation: The first '*' can match the empty string, and the second '*' can match the string 'dce'. 例5：
Enter: s = 'acdcb' p = 'a*c?b' Type: false 問題解決
この質問と前の質問 Leetcode 10：正規表現マッチング（最も詳細なソリューション!!!） それは非常に似ており、前のものよりも簡単です。少し前に変更する必要があります。この問題のアイデアについて少し話しましょう。この問題の難しさは、質問に一致する回数を判断することにあります*。したがって、最も単純な状況から始めたいと思うかもしれません。最初に判断しますp最初の要素は*ではありません。場合p最初の要素は*それからそれについて考える必要があります。*それはゼロに一致するのか、それとも1回一致するのか、つまり判断するだけでよいisMatch(s[1:],p) with isMatch(s,p[1:])。
場合p最初の要素はそうではありません*判断するだけならs[0]対p[0]一致できます。したがって、動的計画法の伝達方程式を非常に迅速に書くことができます。
- f（i、j）= f（i、j − 1）orf（i − 1、j）ifp [j − 1] = ′∗′ f（i、j）= f（i、j-1）または f（i-1、j） if p [j-1] =＆＃x27 *＆＃x27
- f（i、j）= f（i − 1、j − 1）および（s [i − 1] = = p [j − 1] ∣ ∣ p [j − 1] = = ′？′）ifp [j − 1]≠ ′∗′ f（i、j）= f（i-1、j-1）\および\（s [i-1] == p [j-1] || p [j- 1] ==＆＃x27？＆＃x27） if p [j-1] neq＆＃x27 *＆＃x27
f(i,j)高速入力s[0:i]および入力p[0:j]一致の結果。特定の思考変換プロセスは、前の記事を読むことができます。
class Solution: def isMatch(self, s, p): ''' :type s: str :type p: str :rtype: bool ''' s_len, p_len = len(s), len(p) mem = [[False]*(p_len + 1) for _ in range(s_len + 1)] mem[0][0] = True for i in range(s_len + 1): for j in range(1, p_len + 1): if p[j-1] == '*': mem[i][j] = mem[i][j-1] or (i > 0 and mem[i-1][j]) else: mem[i][j] = i > 0 and mem[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '?') return mem[-1][-1] この問題は比較的単純なので、正面から直接解決できます。最初にトラバースしますs with p
s: a d c e b i p: * a * b j 発見j指し示す要素は*記録した*場所と時間i場所、次にj++次の位置を決定します。
s: a d c e b i p: * a * b j star:0 i_index:0 次に、i with j要素が同じを指しているかどうかを判断します。そうであれば、i++j++。
s: a d c e b i p: * a * b j star:0 i_index:0 この時点でj指定された要素は*であり、以前と同じように動作します。
s: a d c e b i p: * a * b j star:2 i_index:1 この時点で、jどちらの点も*、i with j指定された要素が等しくないことがわかりました。振り返る必要があります*現時点でわかっている*場所なので、直接i++はい、つまり*この時点で2回一致します。
s: a d c e b i p: * a * b j star:2 i_index:1 同上、別の注文をしますi++。
s: a d c e b i p: * a * b j star:2 i_index:1 この時点で、i with jが指している要素が同じであることがわかったので、i++j++この時点で、一致が終了し、一致が成功したことがわかりました。
上記のプロセス全体を確認しましょう。いくつかの抜け穴があります。まず、上記の3つの条件のいずれも存在しない場合、直接戻ります。false。終わりに一致する場合（s一致）、jが指している要素と、それに続くすべての要素は*要素の外側で、falseを返します。
class Solution: def isMatch(self, s, p): ''' :type s: str :type p: str :rtype: bool ''' s_len, p_len = len(s), len(p) i, j, star, i_index = 0, 0, -1, 0 while i < s_len: if j < p_len and (p[j] == '?' or p[j] == s[i]): i += 1 j += 1 elif j < p_len and p[j] == '*': star = j j += 1 i_index = i elif star != -1: j = star + 1 i_index += 1 i = i_index else: return False while j < p_len and p[j] == '*': j += 1 return j == p_len 参照：
質問の他の言語バージョンを自分に追加しました GitHub Leetcode
ご不明な点がございましたら、皆様のご指摘をお待ちしております！ ！ ！