472.

class Trie:
    __slots__ = ['children', 'word']

    def __init__(self):
        self.children = defaultdict(Trie)
        self.word = False

    def add(self, word: str) -> None:
        cur = self
        for c in word:
            cur = cur.children[c]
        cur.word = True


class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        trie = Trie()
        for w in words:
            trie.add(w)

        ans = []
        for w in words:
            W = len(w)

            to_check = [0]
            matched = False

            while to_check:
                i = heappop(to_check)
                while to_check and to_check[0] == i:
                    heappop(to_check)

                cur_trie = trie
                for j in range(i, W):
                    if w[j] not in cur_trie.children:
                        break

                    cur_trie = cur_trie.children[w[j]]

                    if not cur_trie.word:
                        continue

                    if j == W - 1 and i != 0:
                        matched = True
                    else:
                        heappush(to_check, j + 1)

                if matched:
                    break

            if matched:
                ans.append(w)

        return ans