[LeetCode] 472. Concatenated Words

- Problem

472. Concatenated Words

간만에 trie 느낌나는 문제

- 내 풀이 (Trie)

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root

        for w in word:
            if w not in curr.children:
                curr.children[w] = TrieNode()
            curr = curr.children[w]
        
        curr.is_word = True

    def is_concatenated(self, word: str, cnt: int = 0) -> bool:
        if not word:
            return cnt >= 2
        
        curr = self.root

        for i, c in enumerate(word):
            if c in curr.children:
                curr = curr.children[c]
                if curr.is_word:
                    if self.is_concatenated(word[i+1:], cnt+1):
                        return True
            
            else:
                return False


class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        trie = Trie()

        for word in words:
            trie.insert(word)
        
        return [word for word in words if trie.is_concatenated(word)]

- 결과

두 시간 정도 붙잡고 나니 불현듯 이런 생각이 들었다.
굳이 trie로 풀어야 하나?

- 다른 풀이 (more efficient)

class Solution:
    def __init__(self):
        self.dp: set = set()
        self.words: set = set()

    def is_concatenated(self, word: str) -> bool:
        if word in self.dp:
            return True

        for i in range(len(word)):
            if word[:i] in self.words:
                if word[i:] in self.words or self.is_concatenated(word[i:]):
                    self.dp.add(word)
                    return True

        return False

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

        return [word for word in words if self.is_concatenated(word)]

- 결과

편안.