23.01.27 Today’s Leetcode

472. Concatenated Words (hard)

꼼수를 이용하려고 했으나, 4 testcase만 통과

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        words.sort(key= lambda x : len(x))
        max_len = len(words[-1])
        temp = set()
        # print(words)
        
        def dfs(cur):
            if len(cur) > max_len:
                return
            for word in temp:
                temp.add(cur + word)
                dfs(cur + word)

        for word in words:
            dfs(word)

        res = [word for word in words if word in temp]
        return res
            

원래 하려던 방식! DFS를 이용한 풀이.

class Solution(object):

    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        d = set(words)

        def dfs(word):
            for i in range(1, len(word)):
                prefix = word[:i]
                suffix = word[i:]
                
                if prefix in d and suffix in d:
                    return True
                if prefix in d and dfs(suffix):
                    return True
                if suffix in d and dfs(prefix):
                    return True
            
            return False
        
        res = [word for word in words if dfs(word)]        
        return res