Hard

题目描述

给定一个不含重复字符串的数组 words，返回其中所有由数组中其他字符串组成的连接词。

连接词的定义为：一个字符串完全由数组中的其他字符串连接形成（至少由两个较短的字符串组成，这些字符串不必不同）。

示例 1：

输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
解释："catsdogcats" 可以由 "cats", "dog" 和 "cats" 连接而成；
     "dogcatsdog" 可以由 "dog", "cats" 和 "dog" 连接而成；
     "ratcatdogcat" 可以由 "rat", "cat", "dog" 和 "cat" 连接而成。

示例 2：

输入：words = ["cat","dog","catdog"]
输出：["catdog"]

提示：

  • 1 <= words.length <= 10^4
  • 1 <= words[i].length <= 30
  • words[i] 仅由小写英文字母组成
  • words 中的所有字符串都是唯一的
  • 1 <= sum(words[i].length) <= 10^5

解题思路

这道题要求找出所有由其他单词连接而成的词。可以用以下几种方法解决：

方法一：排序 + 动态规划 核心思想是先按长度排序，这样在检查一个单词时，所有可能的组成部分都已经被处理过了。对于每个单词，使用动态规划判断是否可以由已知单词组成。

方法二：Trie + DFS 构建字典树存储所有单词，然后对每个单词进行DFS搜索，看能否分解为多个已知单词。

方法三：记忆化搜索 使用哈希集合存储单词，对每个目标单词进行递归分解，用记忆化避免重复计算。

这里采用排序 + 动态规划的方法，因为它思路清晰且效率较高。首先按长度排序确保处理顺序正确，然后用DP检查每个单词是否可以由之前处理过的单词组成。DP状态dp[i]表示前i个字符是否可以由已知单词组成，转移方程为：对于位置j到i的子串，如果dp[j]为真且该子串存在于字典中，则dp[i]为真。

代码实现

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> dict;
        vector<string> result;
        
        // 按长度排序
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.length() < b.length();
        });
        
        for (const string& word : words) {
            if (canForm(word, dict)) {
                result.push_back(word);
            }
            dict.insert(word);
        }
        
        return result;
    }
    
private:
    bool canForm(const string& word, const unordered_set<string>& dict) {
        if (dict.empty()) return false;
        
        int n = word.length();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.count(word.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        word_set = set()
        result = []
        
        # 按长度排序
        words.sort(key=len)
        
        for word in words:
            if self.canForm(word, word_set):
                result.append(word)
            word_set.add(word)
        
        return result
    
    def canForm(self, word: str, word_set: set) -> bool:
        if not word_set:
            return False
        
        n = len(word)
        dp = [False] * (n + 1)
        dp[0] = True
        
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and word[j:i] in word_set:
                    dp[i] = True
                    break
        
        return dp[n]

public class Solution {
    public IList<string> FindAllConcatenatedWordsInADict(string[] words) {
        HashSet<string> wordSet = new HashSet<string>();
        List<string> result = new List<string>();
        
        // 按长度排序
        Array.Sort(words, (a, b) => a.Length.CompareTo(b.Length));
        
        foreach (string word in words) {
            if (CanForm(word, wordSet)) {
                result.Add(word);
            }
            wordSet.Add(word);
        }
        
        return result;
    }
    
    private bool CanForm(string word, HashSet<string> wordSet) {
        if (wordSet.Count == 0) return false;
        
        int n = word.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.Contains(word.Substring(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

var findAllConcatenatedWordsInADict = function(words) {
    const wordSet = new Set(words);
    const memo = new Map();
    
    function canForm(word, count = 0) {
        if (memo.has(word)) return memo.get(word);
        
        for (let i = 1; i <= word.length; i++) {
            const prefix = word.substring(0, i);
            const suffix = word.substring(i);
            
            if (wordSet.has(prefix)) {
                if (suffix === "" && count >= 1) {
                    memo.set(word, true);
                    return true;
                }
                if (suffix !== "" && canForm(suffix, count + 1)) {
                    memo.set(word, true);
                    return true;
                }
            }
        }
        
        memo.set(word, false);
        return false;
    }
    
    return words.filter(word => canForm(word));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m × k)，其中n是单词数量，m是平均单词长度，k是检查子串的平均次数
空间复杂度O(n × m)，用于存储哈希集合和DP数组

相关题目