貪欲探索法についてです
定義
シンプルにまとめると、問題の解に対して複数のオプションがある際に、それぞれを評価し、最適値が高い順に評価していく探索法です
解説および参考
知ることになった経緯
この問題です。解説をみると、文字列SとTをreverseしてそれぞれマッチするかどうか探索していくやり方を用いています.
ちなみに
この問題、JavaだとGreedy法を使うことなく解けます.
というか、C++でできるような、substring()
で開始位置から何文字を切り取る、というやり方が標準的にはできないので、(JavaのSubstringの引数は開始文字indexと終了文字index)
サクッとreplace()
を使ってターゲット文字列があれば""
に置き換えてしまっちゃう方法です。
replace()
は文字にあるターゲット文字全てを置き換えてくれるため、最終的にs.length()
が`0なのかそれ以上なのかで判別が可能です