2

a-z、.、*、および からの文字を含む別の文字列を指定すると、これが問題になりますa-z。where*はその前の文字を削除できます。それ以外の場合、* はスキップされ、.任意の 1 文字に一致します。問題は、最初の文字列が 2 番目の文字列と一致するかどうかです。

注:これは私が見つけた問題のステートメントですが、この場合、文字は正規表現*と同じ機能を実行します。?

例：

isMatch("a*", "") = true; //"a*" could be "a" or an empty string ""
isMatch(".", "") = false; 
isMatch("ab*", "a") = true; 
isMatch("a.", "ab") = true; 
isMatch("a", "a") = true;

この問題は、わずかに変更された編集距離を使用して既に解決していますが、これは 2D 動的計画法のアプローチしか知りません。この問題の線形ソリューションが存在するかどうかは疑問ですが、dp アプローチなしで解決できるのでしょうか?

4

1 に答える 1

1

アドバイスをくれた@RealzSlawに感謝します。私の質問は線形ソリューションを探していましたが、単にこのケースのために(現在は正規表現構文を使用して)、不可能のようです:

isMatch("a?a?b?b?b?a?a?b?a?","abbab")

abbabがの部分列であるかどうかを尋ねますaabbbaaba。私の知る限り、これは NP 困難であるため、線形解は実行不可能なようです。

于 2013-10-22T19:28:54.590 に答える