Pythonで2つの文が類似しているかどうかを判定するプログラムの書き方

2つの文 s と t が与えられたとき、それらが「類似」しているかどうかを判定する問題を考えてみましょう。ここで扱う文は英字のみで構成されているものとします。2つの文が類似しているとは、どちらか一方の文の中に任意の文(空文字列でも可)を挿入することで、両者が完全に等しくなる場合を指します。

例えば、s = "we live at city Kolkata"、t = "city Kolkata" という入力の場合、出力は True になります。これは、t に文 "we live at" を追加することで s と一致させられるためです。

解法のアプローチ

この問題は、次の手順で解くことができます。

• s1 := s を単語ごとに分割したリスト
• s2 := t を単語ごとに分割したリスト
• s1 の要素数が s2 より大きい場合、s1 と s2 を入れ替える
• s1 が空になるまで以下を繰り返す:
  • s2[0] と s1[0](先頭の単語)が一致するなら、両者の先頭の単語を削除する
  • そうでなく、s2[-1] と s1[-1](末尾の単語)が一致するなら、両者の末尾の単語を削除する
  • どちらも一致しない場合は false を返す
• ループを抜けたら true を返す

考え方のポイント

短い方の文の単語列は、長い方の文の「先頭側」と「末尾側」に連続して現れる必要があります。つまり、挿入される部分は必ず両端のいずれかに接しています。この性質を利用すると、両端から順に一致する単語を取り除いていくだけで判定が可能になります。

実装例(Python)

以下のコードで実際の動作を確認してみましょう。

def solve(s, t):
   s1 = s.split()
   s2 = t.split()
   if len(s1) > len(s2):
      s1, s2 = s2, s1
   while(s1):
      if(s2[0]==s1[0]):
         s2.pop(0)
         s1.pop(0)
      elif(s2[-1]==s1[-1]):
         s2.pop()
         s1.pop()
      else:
         return(False)
   return(True)

s = "we live at city Kolkata"
t = "city Kolkata"
print(solve(s, t))

入力

"we live at city Kolkata", "city Kolkata"

出力

True

処理の流れを詳しく解説

このアルゴリズムでは、まず単語数の少ない方を s1 として設定します。その後、s1 が空になるまで次の処理を繰り返します。

1. 両文の先頭の単語を比較し、一致していればそれぞれの先頭を取り除く
2. 先頭が一致しない場合は、両文の末尾の単語を比較し、一致していれば取り除く
3. どちらも一致しなければ、類似した文ではないため False を返す

ループが正常に完了して s1 が空になれば、短い方の文のすべての単語を長い方の文の両端から消費できたことになります。このとき、残った部分(= 挿入された文)が中央にあっても構わない点に注意してください。先頭と末尾の両方から削除を進めることで、挿入位置がどこであっても正しく判定できます。

計算量と最適化のヒント

時間計算量は O(n + m)(n、m はそれぞれの文の単語数)ですが、Python のリストにおける pop(0) は先頭要素の削除に O(n) のコストがかかるため、単語数が多い場合は collections.deque を使って popleft() で先頭を取り除くとより効率的になります。空間計算量は O(n + m) です。