Python DFS Solution


  • 0
    class Solution(object):
        def findAllConcatenatedWordsInADict(self, words):
            """
            :type words: List[str]
            :rtype: List[str]
            """
            s, ans = set(words), []
            def dfs(string):
                if string in s:
                    return True
                for i in xrange(len(string)):
                    if string[:i] in s and dfs(string[i:]):
                        return True
                return False
            for word in words:
                for i in xrange(1, len(word)):
                    if word[:i] in s and dfs(word[i:]):
                        ans.append(word)
                        break
            return ans
    

  • 0
    L

    Time complexity of this is terrible, doesn't even submit


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.