Letcode 10正規表現マッチング
leetcode問題文
入力文字列sとパターンpを指定すると、''*'場所:
」任意の1文字にマッチします. ’*’ 前の要素の0個以上にマッチします.マッチングは、入力文字列全体をカバーする必要があります.
例:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
初期思考
困難な問題…これを解決するためにどんなパターンを適用できますか?
破壊する
この作品を破片で破って、例を見てみましょう.
例1 :
どうやってこれに近づくの?我々は、文字を比較し、比較することができます.もしそれらが等しいなら、次の文字集合を比較することができます.
In this example, we run out of characters for the pattern but still have characters in the string. This scenario indicates we don’t have a match. This is the case because we are looking for a full match, not partial.
テイクアウト
パターンの最後に到達すると、残りの文字列の長さを確認できます.それがゼロに等しいならば、我々は試合をします.そうでなければ、我々はしない.
例2 :
取り扱い"*"
この例を歩いた後に、パターン内の"*"でケースを扱う方法を理解すべきです.
Definition of ”*”: Matches zero or more of the preceding character in the pattern.
定義を読むと、我々は2つの方法でマッチできる.
このオプションはoption 1かoption 2に存在する.我々は確かに両方を知る必要があります知っている.
Note: Whenever we run into problems where we need to explore multiple paths, recursion can be an effective tool. Uncovering this indicates that we could use recursion to solve this, and that’s what we will be doing. If you are not familiar with recursion, I’d recommend to learn the pattern first and then come back to this post.
例を踏む
再帰的に、例を通して作業をしましょう.
最初の文字を比較し、それらが等しいことを確認できます.
"*"を持っているかどうかを確認するには、"p "の次の文字を見なければなりません."*"であれば、両方のオプションを扱う必要があります.
最初のケースを扱う(レベル1 )
ケース1:ゼロ出現
アクション:“P”の文字を無視して
パターンの末尾に達したが、文字列ではないので、
2番目のケースを扱う(レベル1 )
ケース2 :前の文字の1つ以上の出現
次の文字をチェックする
ここに着いたら、もう一度キャラクターを比較する.彼らがマッチして、Pの次のキャラクタが「*」であるので、我々は再び我々の2つのケースを調査します.
最初のケースを扱う(レベル2 )
ケース1:ゼロ出現
アクション:“P”の文字を無視して
我々は“P”で先にジャンプしますが、我々はまだ“s”に残っている文字を持っているでしょう.したがって、これはfalseに評価されます.
2番目のケースを扱う(レベル2 )
ケース2 :前の文字の1つ以上の出現
次の文字をチェックする
我々は、“S”で先にジャンプし、“S”の最後に到達する.しかしながら、我々はまだ「P」で性格を持ちます.それで、もう一度、我々は「P」で次のキャラクタをチェックして、「*」ケースを特定して、2つのケースを調査します.我々が行くスタックのより深い!
最初のcase ( level 3 )の処理
ケース1:ゼロ出現
アクション:“P”の文字を無視して
今回は、両方の文字列の末尾に到達しました.これはマッチがあることを意味します.
2番目のケースを扱う(レベル3 )
ケース2 :前の文字の1つ以上の出現
次の文字をチェックする
ここでは、我々は前方にsで移動して、境界からあります.ここで比較する性格がないので、我々はfalseを返します.
Note: We are exploring this case for completeness, but depending on how we implement our algorithm we could just stop exploring once we find a true case.
テイクアウト
再帰は、2つの可能な経路を探索しなければならないので、これを解決する良い方法です.
例3
この例では""この文字は任意の文字にマッチできることを示します.この場合、“＊”が続きますので、最後の例で学んだケースを適用します.
最初のケースを扱う(レベル1 )
ケース1:ゼロ出現
アクション:“P”の文字を無視して
この場合、私たちは「p」でキャラクタを使い果たすでしょう、しかし、我々はまだ「s」でキャラクタを持っています.したがって、このケースはfalse
2番目のケースを扱う(レベル1 )
ケース2 :前の文字の1つ以上の出現
次の文字をチェックする
から"."任意の文字を等しくすることができます.そこから、我々は再び我々の2つのケースを評価します.
最初のケースを扱う(レベル2 )
ケース1:ゼロ出現
アクション:“P”の文字を無視して
以前と同様に、“p”の文字がなくなったので、これはfalseに評価されます.
2番目のケースを扱う(レベル2 )
ケース2 :前の文字の1つ以上の出現
次の文字をチェックする
このケースは前の例からよくわかります.私たちは“s”で1文字前に移動します任意の文字にマッチします.ここで到達したら、私たちは最終的に本当の評価をすることができます.
Nice! Stepping through these examples have helped us understand the cases we will have to handle. Now that we have a good understanding of the problem, lets lay our thoughts out so we can code it up.
アルゴリズム計画
我々が発見したように、我々は問題を解決するために再帰的なアプローチを使用しています.それを念頭に置いて、我々のベースケースを特定しましょう
ベースケース:
コード
const isMatch = (s, p, sIdx = 0, pIdx = 0) => {
if (p.length === pIdx) {
return s.length === sIdx;
}
const firstMatch = sIdx < s.length && (s[sIdx] === p[pIdx] || p[pIdx] === ".");
if ((pIdx + 1) < p.length && p[pIdx + 1] === "*") {
return (
isMatch(s, p, sIdx, pIdx + 2) // Case One
|| firstMatch && isMatch(s, p, sIdx + 1, pIdx) // Case Two
)
}
return firstMatch && isMatch(s, p, sIdx + 1, pIdx + 1);
}
概要
最悪の場合、このアルゴリズムはO((s＋p)×2 ^ s＋p/2)であり、sとpはそれぞれsとpの長さである.この時間の複雑さは、ピンダウンに非常に挑戦的です.私は、深いダイビングのためにこのblog postを推薦します.
再帰的にこの問題を通して働くことは、解決策を考え出すことに関係していることを理解するのに役立ちます.しかし,この問題への最適解は動的計画法で達成できる.この問題に対する動的プログラミング解はo(s＊p)で実行される.
あなたが最初にあなたの頭を包むのは難しいことができます動的プログラミングに精通していない場合.しかし、一度パターンを適用する方法を理解すると、それはあなたが最小限のコードでパフォーマンスのソリューションを思い付くことができます.それは非常に強力なパターンです.
私は、我々が学んだものをとって、ダイナミックなプログラミングでこの問題を解決しようとするようにあなたに挑戦します.私も自分自身に挑戦します!
これが役に立つという望み!
Reference
この問題について(Letcode 10正規表現マッチング), 我々は、より多くの情報をここで見つけました https://dev.to/vickdayaram/leetcode-10-regular-expression-matching-3eemテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol