Pythonで文字列sの部分列となる単語の個数を数えるプログラム

問題概要

単語のリスト words と文字列 s が与えられます。このとき、words に含まれる文字列のうち、s の部分列（サブシーケンス）になっているものの個数を求めるのが目標です。

ここで「部分列」とは、元の文字列から一部の文字を削除して（文字の並び順は変えずに）得られる文字列のことを指します。たとえば、words = ["xz", "xw", "y"]、s = "xyz" という入力の場合、「xz」と「y」はどちらも「xyz」の部分列であるため、答えは 2 になります。

解法のアプローチ

各単語ごとに s を何度も走査すると非効率です。そこで、先頭文字ごとに単語をバケット（グループ）に分けて管理するのがポイントです。こうすることで、s を一度だけ走査すればすべての判定が完了します。

具体的な手順は次のとおりです。

• 答えを格納する変数 ans を 0 で初期化します。
• 先頭文字をキーとする辞書 d を用意します。
• words 内の各単語を、その先頭文字をキーとして d に登録します。
• s を先頭から 1 文字ずつ走査します。現在の文字 c に対応するバケット d[c] を取り出し、中身を空にします。
• 取り出した各単語について、長さが 1 であれば s 内で完全にマッチしたことになるので ans を 1 増やします。まだ残りの文字がある場合は、先頭の 1 文字を除いた残りを、新しい先頭文字のバケットに再登録します。
• 最後に ans を返します。

実装例

from collections import defaultdict
class Solution:
   def solve(self, words, s):
      ans = 0

      d = defaultdict(list)
      for word in words:
         d[word[0]].append(word)

      for c in s:
         l = d[c]
         d[c] = []

         for word in l:
            if len(word) == 1:
               ans += 1
            else:
               d[word[1]].append(word[1:])
      return ans
ob = Solution()
words = ["xz", "xw", "y"]
s = "xyz"
print(ob.solve(words, s))

入力

["xz", "xw", "y"], "xyz"

出力

2

計算量

このアルゴリズムの時間計算量は O(M + N) です。ここで M は文字列 s の長さ、N はすべての単語の文字数の合計です。各単語の各文字は走査中にちょうど 1 回だけ処理されるため、単語ごとに s を調べる素朴な二重ループ（O(len(words) × len(s))）よりも大幅に効率的です。空間計算量は O(N) となります。