1.题目基本信息

1.1.题目描述

给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。

连接词 定义为：一个完全由给定数组中的至少两个较短单词（不一定是不同的两个单词）组成的字符串。

1.2.题目地址

https://leetcode.cn/problems/concatenated-words/description/

2.解题方法

2.1.解题思路

字典树

2.2.解题步骤

主函数步骤：

• 第一步，将words按长度进行升序排列

• 第二步，依次遍历单词。如果合法，则加入结果数组；否则插入到字典树

记忆化搜索步骤：

• 第一步，递归退出条件。由于不会有重复单词，所以index==len(word)的情况一定是合法的

• 第二步，记忆化搜索过去状态，并更新缓存表

• 第三步，遍历字符，如果匹配单词，则递归判断剩余的子串是否合法

3.解题代码

python代码

class Trie():
    def __init__(self):
        self.children = {}
        self.end = False
    
    def insert(self, word):
        cur = self
        for c in word:
            if c not in cur.children:
                cur.children[c] = Trie()
            cur = cur.children[c]
        cur.end = True
    
    def find(self, word):
        cur = self
        for c in word:
            if c not in cur.children:
                return 0
            cur = cur.children[c]
        return 1 if cur.end else 2
    
    # 递归任务：返回word[index:]子串是否能由当前字典树中的短单词连接而成
    def dfs(self, index, word, visited) -> bool:
        # 第一步，递归退出条件。由于不会有重复单词，所以index==len(word)的情况一定是合法的
        if index == len(word):
            return True
        # 第二步，记忆化搜索过去状态，并更新缓存表
        if visited[index]:
            # 如果又到了之前的状态，说明之前的状态没有成功，否则就不会到这一步了
            return False
        visited[index] = True
        # 第三步，遍历字符，如果匹配单词，则递归判断剩余的子串是否合法
        cur = self
        for i in range(index, len(word)):
            c = word[i]
            if c not in cur.children:
                return False
            if cur.children[c].end and self.dfs(i + 1, word, visited):
                return True
            cur = cur.children[c]
        return False


class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        # 思路：字典树
        # 第一步，将words按长度进行升序排列
        words.sort(key = len)
        # 第二步，依次遍历单词。如果合法，则加入结果数组；否则插入到字典树
        trie = Trie()
        result = []
        for word in words:
            if word == "":
                continue
            if trie.dfs(0, word, [False] * len(word)):
                result.append(word)
            else:
                trie.insert(word)
        return result

4.执行结果