Leetcode Problem 472 Concatenated Words.txt

472. Concatenated Words
Given a list of words (without duplicates), please write a program that returns all 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:
Input: ["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".
Note:
The number of elements of the given array will not exceed 10,000
The length sum of elements in the given array will not exceed 600,000.
All the input string will only include lower case letters.
The returned elements order does not matter.


Hint to solve: Use dfs for every word. Loop through each index in the word and calculate the prefix and suffix. Use memoization to store the intermediate results.


class Solution:
    
    def Dfs(self, word) -> bool:
        
        for i in range(1, len(word)):
            prefix = word[:i]
            suffix = word[i:]
            
            if word in self.memo and self.memo[word] == True:
                return True
            
            if prefix in self.wordSet and suffix in self.wordSet:
                self.memo[word] = True
                return True
            
            if prefix in self.wordSet and self.Dfs(suffix):
                self.memo[word] = True
                return True
        
        self.memo[word] = False
        return False
    
    
    
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        
        self.wordSet = set(words)
        self.memo = {}
        result = []
        
        for word in words:
            if self.Dfs(word):
                result.append(word)
        return result;