跳到主要内容

472.连接词

· 阅读需 4 分钟

1、题干​

给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 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 <= 104
  • 1 <= words[i].length <= 30
  • words[i] 仅由小写英文字母组成。 
  • words 中的所有字符串都是 唯一 的。
  • 1 <= sum(words[i].length) <= 105

常规解法用字典树处理，详情可以看官解。 补充：这个解法有漏洞，调整用例肯定还会超时

2、解题思路​

这里采用一种非常规解法，创建哈希集合set并加入所有单词，然后遍历所有单词并判断该单词是否由set中的元素组成，判断过程是利用递归对每个单词进行分段，如果set包含所有分段后的子串则说明其是连接词。

然后写出了下面这段代码，结果通过用例43/44，最后一个用例超时。主要是因为这个用例的特殊性，导致递归检查函数的执行次数暴涨。

var findAllConcatenatedWordsInADict = function (words) {
    const set = new Set(words);
    if (set.has("")) set.delete("");

    function dfs(word, start) {
        let s = '';
        for (let i = start; i < word.length; i++) {
            s += word[i];
            if (set.has(s) && dfs(word, i + 1)) return true;
        }
        return set.has(s) && start;
    }

    return words.reduce((acc, cur) => (dfs(cur, 0) && acc.push(cur), acc), []);
};

由于该用例的特殊性，尝试添加预检策略绕过一些特殊用例：

  • 1、字符串数组按长度升序排序，由于长单词肯定由短单词组成，意味着如果前面的短单词无法组合出当前单词的特征，就说明其不是连接词
  • 2、预检函数，取出单词中所有连续的两个字符（最短连接子串），检查更短的单词是否包含或能组合出这个最短连接子串，如果为否则说明其不是连接词

3、完整代码​

var findAllConcatenatedWordsInADict = function (words) {
    words.sort((a, b) => a.length - b.length);
    const set = new Set(words);
    if (set.has('')) set.delete('');

    function dfs(word, start) {
        let s = '';
        for (let i = start; i < word.length; i++) {
            s += word[i];
            if (set.has(s) && dfs(word, i + 1)) return true;
        }
        return set.has(s) && start;
    }

    const headSet = new Set(), tailSet = new Set(), compSet = new Set();
    function preCheck(word) {
        let found = true, comps = [];
        for (let i = 0; i < word.length - 1; i++) {
            const s = word[i] + word[i + 1];
            if (!compSet.has(s) && !(tailSet.has(s[0]) && headSet.has(s[1]))) found = false;
            comps.push(s);
        }
        headSet.add(word[0]), tailSet.add(word[word.length - 1]);
        for (const c of comps) compSet.add(c);
        return found;
    }

    return words.reduce((acc, cur) => {
        if (!preCheck(cur)) return acc;
        if (dfs(cur, 0)) acc.push(cur);
        return acc;
    }, []);
};

4、执行结果​

1.png