关于#lc-472#的问题，请各位专家解答！

Question

class Solution:

    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        trie = Trie()
        for word in words:
            trie.insert(word)

        sorted(words, key=lambda a: len(a))
        visited = dict()

        def dfs(word: str, i: int) -> bool:
            if i == len(word):
                return True

            if word[i:] in visited:
                return visited[word[i:]]

            flag = False
            q = trie.search(word[i:])
            for j in q:
                flag |= bool(i) and dfs(word, i + j + 1)

            visited[word[i:]] = flag

            return flag

        ans = list()

        for word in words:
            q = trie.search(word)
            q.pop()
            for i in q:
                if dfs(word, i + 1):
                    ans.append(word)
                    break

        return ans


class Trie:
    def __init__(self) -> None:
        self.links = dict()
        self.isEnd = False

    def put(self, c: str) -> None:
        self.links[c] = Trie()

    def get(self, c: str) -> 'Trie':
        return self.links.get(c, None)

    def containsKey(self, c) -> bool:
        return c in self.links

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            if c not in node.links:
                node.put(c)
            node = node.links[c]
        node.isEnd = True

    def search(self, word: str) -> List[int]:
        ans = list()
        node = self
        for i, c in enumerate(word):
            if not node.containsKey(c):
                return ans
            node = node.links[c]
            if node.isEnd:
                ans.append(i)

        return ans

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题解答

问题是关于 LeetCode 第 472 题 "Find All Concatenated Words in a Dictionary" 的实现，使用 Python 语言。

问题描述：给定一个字典 words 和一个字符串 sentence，返回所有在字典中可以拼接成 sentence 的单词列表。

解决方案

可以使用 Trie 数据结构来实现。首先，遍历字典 words，构建 Trie 树。然后，遍历 sentence，使用 Trie 树来判断是否可以拼接成 sentence。

以下是核心代码：

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

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.is_word = True

        result = []
        for word in words:
            if self.isConcatenated(root, word):
                result.append(word)

        return result

    def isConcatenated(self, node, word):
        if not node:
            return False
        if node.is_word:
            return True
        for i in range(1, len(word) + 1):
            if word[:i] in node.children and self.isConcatenated(node.children[word[:i]], word[i:]):
                return True
        return False

解释

1. 首先，构建 Trie 树，遍历字典 words，构建 Trie 树。
2. 然后，遍历 sentence，使用 Trie 树来判断是否可以拼接成 sentence。
3. 在 isConcatenated 函数中，我们遍历 word，检查是否可以拼接成 sentence。如果可以，返回 True，否则返回 False。

时间复杂度

时间复杂度为 O(n)，其中 n 是字典 words 的长度。

空间复杂度

空间复杂度为 O(n)，其中 n 是字典 words 的长度。