単語の連結の数を数えるプログラムは、Pythonのリストにあります

文字列のリストがあるとします。リスト内で他の単語を連結した単語の数を見つける必要があります。連結時に単語を再利用したり、何度でも連結したりできます。

したがって、入力がwords =["hello"、 "world"、 "helloworld"、 "famous"、 "worldfamous"、 "programming"]の場合、"helloworld"は"の連結であるため、出力は2になります。こんにちは」と「世界」。 「worldfamous」は「world」と「famous」を連結したものです。

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

• トライ：=新しい地図
• 単語内の各単語について、
  • layer：=trie
  • 単語のwごとに、
    • wがレイヤーにない場合は、
      • layer [w]：=新しいマップ
    • layer：=layer [w]
  • layer ["*"]：=空のタプル
  • 関数dfs（）を定義します。これには、num_concatenated_wordsという単語が必要です
  • layer：=trie
  • 単語内の各インデックスiと単語wについて、実行します
    • 「*」がレイヤーにある場合、
      • dfs（word [インデックスiから終了まで]、num_concatenated_words + 1）がTrueの場合、
        • Trueを返す
      • wがレイヤーにない場合は、
        • Falseを返す
    • layer：=layer [w]
  • 「*」がレイヤーにあり、num_concatenated_words> =1の場合、
    • Trueを返す
  • Falseを返す
  • メインの方法から、次の手順を実行します。
  • count：=0
  • 単語内の各単語について、
    • count：=count + dfs（word、0）
• 返品数

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

例

class Solution:
   def solve(self, words):
      trie = {}
      for word in words:
         layer = trie
         for w in word:
            if w not in layer:
               layer[w] = {}
            layer = layer[w]
         layer["*"] = ()

      def dfs(word, num_concatenated_words):
         layer = trie

         for i, w in enumerate(word):
            if "*" in layer:
               if dfs(word[i:], num_concatenated_words + 1):
                  return True
            if w not in layer:
               return False
            layer = layer[w]

         if "*" in layer and num_concatenated_words >= 1:
            return True
         return False

      count = 0
     for word in words:
      count += dfs(word, 0)
   return count

ob = Solution()
words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]
print(ob.solve(words))

入力

["hello", "world", "helloworld", "famous", "worldfamous", "programming"]

出力

2