파이썬의 목록에 단어 연결 수를 계산하는 프로그램이 있습니다.

문자열 목록이 있다고 가정합니다. 우리는 또한 목록에서 다른 단어의 연결 단어의 수를 찾아야 합니다. 연결할 때 단어를 재사용하고 여러 번 연결할 수 있습니다.

따라서 입력이 단어 =["hello", "world", "helloworld", "famous", "worldfamous", "programming"]와 같은 경우 출력은 "helloworld"가 "의 연결이므로 2가 됩니다. 안녕하세요"와 "세계". "worldfamous"는 "world"와 "famous"를 연결한 것입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

• trie :=새 지도
• 단어의 각 단어에 대해 수행
  • 레이어 :=시도
  • 단어의 각 w에 대해 수행
    • w가 레이어에 없으면
      • layer[w] :=새 지도
    • 레이어 :=레이어[w]
  • layer["*"] :=빈 튜플
  • dfs() 함수를 정의합니다. num_concatenated_words
  라는 단어가 필요합니다.
  • 레이어 :=시도
  • 단어의 각 색인 i와 단어 w에 대해 do
    • "*"가 레이어에 있으면
      • dfs(word[인덱스 i에서 끝까지], num_concatenated_words + 1)가 True이면
        • 참 반환
      • w가 레이어에 없으면
        • 거짓을 반환
    • 레이어 :=레이어[w]
  • "*"가 레이어에 있고 num_concatenated_words>=1이면
    • 참 반환
  • 거짓을 반환
  • 기본 방법에서 다음을 수행합니다.
  • 카운트:=0
  • 단어의 각 단어에 대해 수행
    • count :=count + dfs(단어, 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