Pythonの単語リスト内に存在するサブシーケンスの数を見つけるプログラム

単語のリストと文字列sがあるとすると、単語リスト内でsのサブシーケンスである文字列の数を見つける必要があります。

したがって、入力がwords =["xz"、 "xw"、 "y"] s ="xyz"の場合、"xz"と"y"は"xyz"のサブシーケンスであるため、出力は2になります。

これを解決するには、次の手順に従います-

• ans：=0
• d：=空の地図
• 単語内の各単語について、
  • d [word [0]]
  の最後に単語を挿入します
• sの各cについて、
  • l：=d [c]
  • d [c]：=新しいリスト
  • lの各単語について、
    • 単語のサイズが1の場合、
      • ans：=ans + 1
    • それ以外の場合、
      • d[word[1]]の最後にword[インデックス1から最後まで]の部分文字列を挿入します
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

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