13

2つの文字列があるとしましょう

AAABBBCCCCC

と

AAAABBBBCCCC

これらの文字列をできるだけ似たものにするために、私がすべき文字しか削除できないことを考えると

  • 最初の文字列から最後の C を削除します
  • 2 番目の文字列から最後の A と最後の B を削除し、

彼らがなるように

AAABBBCCCC

各文字列から削除する文字を見つけるための効率的なアルゴリズムは何でしょうか?

私は現在、文字列の部分文字列を含む解決策を考えて脳細胞を粉砕し、他の文字列でそれらを探しています。

4

4 に答える 4

0

正規表現でこれができると思います。文字列の距離の問題です。つまり。2つの文字列を用意しましょう:

str1 = 'abc'
str2 = 'aabbcc'

まず、短いものを選択し、次のような正規表現を作成します。

regex = '(\w*)'+'(\w*)'.join(list(str1))+'(\w*)'

次に、検索できます。

matches = re.search(regex,str2)

丸括弧を使用して、関心のあるセクションをグループ化します。これらの一致のグループ.group() は 2 つの文字列の距離です.次に、どの文字を削除する必要があるかを判断できます。それは私の考えです、それがあなたを助けることができることを願っています。

于 2012-05-06T11:08:12.277 に答える