動機

與140很像

Problem

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

 

Example 1:

Input: words = [cat,cats,catsdogcats,dog,dogcatsdog,hippopotamuses,rat,ratcatdogcat]Output: [catsdogcats,dogcatsdog,ratcatdogcat]Explanation: catsdogcats can be concatenated by cats, dog and cats; dogcatsdog can be concatenated by dog, cats and dog; ratcatdogcat can be concatenated by rat, cat, dog and cat.

Example 2:

Input: words = [cat,dog,catdog]Output: [catdog]

 

Constraints:

  • 1 <= words.length <= 104
  • 0 <= words[i].length <= 1000
  • words[i] consists of only lowercase English letters.
  • 0 <= sum(words[i].length) <= 105

Sol

都是用dfs去try每個分割點，不過這次的word set要自己造

之後就是dfs去割，割到最後就是有

class Solution:
    def dfs(self,s):
        if not s:
            return True
        for i in range(1,len(s)):
            if s[:i] in self.seen and (s[i:] in self.seen or self.dfs(s[i:])):
                return True
        return False
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        self.seen = set(words)
        self.words = words
        ret = []
        for w in words:
            if w:
                if self.dfs(w):
                    ret.append(w)
        return ret