跳到主要内容

8 篇博文 含有标签「字典树」

查看所有标签

· 阅读需 3 分钟

1、题干​

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。

例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类：

  • StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。
  • boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。

 

示例：

输入：
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
输出：
[null, false, false, false, true, false, true, false, false, false, false, false, true]

解释：
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // 返回 False
streamChecker.query("b"); // 返回 False
streamChecker.query("c"); // 返回n False
streamChecker.query("d"); // 返回 True ，因为 'cd' 在 words 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True ，因为 'f' 在 words 中
streamChecker.query("g"); // 返回 False
streamChecker.query("h"); // 返回 False
streamChecker.query("i"); // 返回 False
streamChecker.query("j"); // 返回 False
streamChecker.query("k"); // 返回 False
streamChecker.query("l"); // 返回 True ，因为 'kl' 在 words 中

 

提示：

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 200
  • words[i] 由小写英文字母组成
  • letter 是一个小写英文字母
  • 最多调用查询 4 * 104 次

2、思路​

  • 构造函数：字典树存储所有单词的逆序串
  • query：数组存储字符流，按字符流逆序查找字典树中是否存在该后缀

3、代码​

class StreamChecker {
    letters = [];
    trie = { end: false };

    constructor(words: string[]) {
        for (const word of words) this.add(word);
    }

    query(letter: string): boolean {
        this.letters.push(letter);
        return this.find(this.letters);
    }

    add(word: string) {
        let t = this.trie;
        for (let i = word.length - 1; i > -1; i--) {
            if (!t[word[i]]) t[word[i]] = { end: false };
            t = t[word[i]];
        }
        t.end = true;
    }

    find(letters: string[]) {
        let t = this.trie;
        for (let i = letters.length - 1; i > -1; i--) {
            t = t[letters[i]];
            if (!t) return false;
            if (t.end) return true;
        }
        return t.end;
    }
}

4、复杂度​

  • 时间复杂度：构造函数 O(mn)O(mn)，query O(mk)O(mk)，其中 n为单词数，m 为单词长度，k 为查询次数
  • 空间复杂度：O(mn+k)O(mn+k)

5、执行结果​

image.png

· 阅读需 4 分钟

1、题干​

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

  • 例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。

 

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。

示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]

 

提示：

  • 1 <= folder.length <= 4 * 104
  • 2 <= folder[i].length <= 100
  • folder[i] 只包含小写字母和 '/'
  • folder[i] 总是以字符 '/' 起始
  • folder 每个元素都是 唯一 的

2、思路1-排序​

  • 对文件夹数组 folder 升序排序，初始化父文件夹 pf = folder[0] + '/'
  • 遍历检查所有文件夹 folder[i] 与当前父文件夹 pf 是否父子关系，是则说明 folder[i] 是子文件夹，不是则将 folder[i] 置为父文件夹继续检查

3、代码​

function removeSubfolders(folder: string[]): string[] {
    folder.sort();

    const ans = [folder[0]];
    let pf = folder[0] + '/';

    for (let i = 1; i < folder.length; i++) {
        if (!folder[i].startsWith(pf)) {
            ans.push(folder[i]);
            pf = folder[i] + '/';
        }
    }

    return ans;
};

4、复杂度​

  • 时间复杂度：O(nm∗logn)O(nm*logn)
  • 空间复杂度：O(logn)O(logn)

5、执行结果​

image.png

6、思路2-哈希​

将 folder 数组中所有文件夹存入哈希集合 set，遍历检查文件夹 folder[i] 所有前缀路径，若前缀路径存在于 set 中，则说明 folder[i] 是子文件夹

7、代码​

function removeSubfolders(folder: string[]): string[] {
    const ans = [], set = new Set(folder);

    for (const f of folder) {
        let found = false;

        for (let i = 0; i < f.length;) {
            i = f.indexOf('/', i + 1);
            if (i < 0) break;

            const dir = f.slice(0, i);

            if (set.has(dir)) {
                found = true;
                break;
            }
        }

        if (!found) ans.push(f);
    }

    return ans;
};

8、复杂度​

  • 时间复杂度：O(nm)O(nm)
  • 空间复杂度：O(nm)O(nm)

9、执行结果​

image.png

· 阅读需 3 分钟

1、题干​

给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

  • 例如， “ace” 是 “abcde” 的子序列。

 

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

 

提示:

  • 1 <= s.length <= 5 * 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • words[i]和s 都只由小写字母组成。
​​​​

Problem: 792. 匹配子序列的单词数

2、思路​

二分查找

  • 按字母表顺序把字符串 s 中所有字符的下标升序存入二维数组 idxMatrix
  • 判断数组 words 中任意字符串 w 是否 s 的子序列，只需要判断 w 中任意字符 c 比前一个字符 在 s 中的下标更大。其中查找 c 在 s 中的下标时，使用二分查找算法

3、Code​

function numMatchingSubseq(s: string, words: string[]): number {
    const CA = 'a'.charCodeAt(0), idxMatrix = new Array(26).fill(0).map(() => []);

    for (let i = 0; i < s.length; i++) {
        const ci = s[i].charCodeAt(0) - CA;
        idxMatrix[ci].push(i);
    }

    function find(nums: number[] = [], k: number) {
        let l = 0, r = nums.length - 1;

        while (l <= r) {
            const m = ((l + r) / 2) >> 0;
            if (nums[m] > k) {
                if (nums[m - 1] > k) r = m - 1;
                else return nums[m];
            } else {
                l = m + 1;
            }
        }

        return -1;
    }

    let res = 0;
    loop: for (const w of words) {
        let preIdx = -1;
        for (const c of w) {
            const ci = c.charCodeAt(0) - CA;
            const ni = find(idxMatrix[ci], preIdx);
            if (ni < 0) continue loop;
            preIdx = ni;
        }
        res++;
    }

    return res;
};

4、复杂度​

  • 时间复杂度：O(n∗logn)O(n*logn)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png

· 阅读需 4 分钟

1、题干​

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类：

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

 

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

 

提示：

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100 次 search

 

注意：本题与主站 676 题相同： https://leetcode-cn.com/problems/implement-magic-dictionary/

2、解法1-字符串比较​

数组存储字典，查找时直接进行字符串比较，如果不匹配的字符数量为1返回true，否则继续查找直至结束返回false

3、代码​

var MagicDictionary = function () {
    this.dict = [];
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    this.dict = dictionary;
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < this.dict.length; i++) {
        if (searchWord.length !== this.dict[i].length) continue;

        let diff = 0;
        for (let j = 0; j < searchWord.length; j++) {
            if (diff > 1) break;
            if (searchWord[j] !== this.dict[i][j]) diff++;
        }

        if (diff === 1) return true;
    }

    return false;
};

4、执行结果​

image.png

5、解法2-哈希表​

哈希表存储字典，查找时对源字符串的每一位做替换，若替换后哈希表存在该字符串则返回true，否则继续查找直至结束返回false

6、代码​

var MagicDictionary = function () {
    this.dict = new Set();
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    for (const w of dictionary) this.dict.add(w);
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < searchWord.length; i++) {
        const pre = searchWord.slice(0, i), post = searchWord.slice(i + 1);
        for (let j = 97; j < 123; j++) {
            const c = String.fromCharCode(j);
            if (c === searchWord[i]) continue;
            if (this.dict.has(pre + c + post)) return true;
        }
    }

    return false;
};

7、执行结果​

  • 执行用时: 860 ms
  • 内存消耗: 48.3 MB

· 阅读需 4 分钟

1、题干​

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类：

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

 

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

 

提示：

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100 次 search

 

注意：本题与主站 676 题相同： https://leetcode-cn.com/problems/implement-magic-dictionary/

2、解法1-字符串比较​

数组存储字典，查找时直接进行字符串比较，如果不匹配的字符数量为1返回true，否则继续查找直至结束返回false

3、代码​

var MagicDictionary = function () {
    this.dict = [];
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    this.dict = dictionary;
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < this.dict.length; i++) {
        if (searchWord.length !== this.dict[i].length) continue;

        let diff = 0;
        for (let j = 0; j < searchWord.length; j++) {
            if (diff > 1) break;
            if (searchWord[j] !== this.dict[i][j]) diff++;
        }

        if (diff === 1) return true;
    }

    return false;
};

4、执行结果​

image.png

5、解法2-哈希表​

哈希表存储字典，查找时对源字符串的每一位做替换，若替换后哈希表存在该字符串则返回true，否则继续查找直至结束返回false

6、代码​

var MagicDictionary = function () {
    this.dict = new Set();
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    for (const w of dictionary) this.dict.add(w);
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < searchWord.length; i++) {
        const pre = searchWord.slice(0, i), post = searchWord.slice(i + 1);
        for (let j = 97; j < 123; j++) {
            const c = String.fromCharCode(j);
            if (c === searchWord[i]) continue;
            if (this.dict.has(pre + c + post)) return true;
        }
    }

    return false;
};

7、执行结果​

  • 执行用时: 860 ms
  • 内存消耗: 48.3 MB

· 阅读需 4 分钟

1、题干​

给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

 

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [0]
输出：0

示例 3：

输入：nums = [2,4]
输出：6

示例 4：

输入：nums = [8,10,2]
输出：10

示例 5：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

 

提示：

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 231 - 1

 

进阶：你可以在 O(n) 的时间解决这个问题吗？

 

注意：本题与主站 421 题相同： https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

题目比较难，没能想到官解那些优秀解法，尝试了暴力解法并两次剪枝优化后，不仅AC还超过82%提交

2、解题思路​

解题关键是：最大异或结果一定是由 二进制位数最多的一个数 与 另一个数 进行异或运算得来。 以 [3,10,5,25,2,8] 为例，用二进制表示是：[11, 1010, 101, 11001, 10, 1000]，其中 二进制位数最多 的只有1个数 25(11001)，接着计算 25 跟其他数的异或结果并取最大值即可。


暴力解法步骤 ：

  • 先对数组进行降序排序
  • 对所有数进行异或运算并取最大值

剪枝优化：

  • 优化1：异或结果的最大可能是：二进制位数最多的数异或之后所有二进制位变成 1，假设为 MAX_NUM。如果运算结果已达到最大可能 MAX_NUM，则直接退出程序。（效果显著）
  • 优化2：异或运算时，第一个数取 二进制位数最多的数 ，第二个数取 二进制位数更少的数 。第一个数不变的情况下，第二个数的二进制位数与其相同则异或会导致最高位变为 0，结果必然小于第二个数的二进制位数更少的情况。

3、代码​

// 优化1
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    let idx = nums.findIndex((n) => n < 1 << c);
    if (idx < 0) idx = nums.length;

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    for (let i = 0; i < idx; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            res = Math.max(res, nums[i] ^ nums[j]);
            if (res === MAX_NUM) return res;
        }
    }

    return res;
};

// 优化1 + 优化2
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    const idx = nums.findIndex((n) => n < 1 << c);

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    if (idx > -1) {
        for (let i = 0; i < idx; i++) {
            for (let j = idx; j < nums.length; j++) {
                res = Math.max(res, nums[i] ^ nums[j]);
                if (res === MAX_NUM) return res;
            }
        }
    } else {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) res = Math.max(res, nums[i] ^ nums[j]);
        }
    }

    return res;
};

4、复杂度​

  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png

· 阅读需 4 分钟

1、题干​

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

 

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

 

提示：

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 231 - 1

 

注意：本题与主站 421 题相同： https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

题目比较难，没能想到官解那些优秀解法，尝试了暴力解法并两次剪枝优化后，不仅AC还超过82%提交

2、解题思路​

解题关键是：最大异或结果一定是由 二进制位数最多的一个数 与 另一个数 进行异或运算得来。 以 [3,10,5,25,2,8] 为例，用二进制表示是：[11, 1010, 101, 11001, 10, 1000]，其中 二进制位数最多 的只有1个数 25(11001)，接着计算 25 跟其他数的异或结果并取最大值即可。


暴力解法步骤 ：

  • 先对数组进行降序排序
  • 对所有数进行异或运算并取最大值

剪枝优化：

  • 优化1：异或结果的最大可能是：二进制位数最多的数异或之后所有二进制位变成 1，假设为 MAX_NUM。如果运算结果已达到最大可能 MAX_NUM，则直接退出程序。（效果显著）
  • 优化2：异或运算时，第一个数取 二进制位数最多的数 ，第二个数取 二进制位数更少的数 。第一个数不变的情况下，第二个数的二进制位数与其相同则异或会导致最高位变为 0，结果必然小于第二个数的二进制位数更少的情况。

3、代码​

// 优化1
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    let idx = nums.findIndex((n) => n < 1 << c);
    if (idx < 0) idx = nums.length;

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    for (let i = 0; i < idx; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            res = Math.max(res, nums[i] ^ nums[j]);
            if (res === MAX_NUM) return res;
        }
    }

    return res;
};

// 优化1 + 优化2
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    const idx = nums.findIndex((n) => n < 1 << c);

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    if (idx > -1) {
        for (let i = 0; i < idx; i++) {
            for (let j = idx; j < nums.length; j++) {
                res = Math.max(res, nums[i] ^ nums[j]);
                if (res === MAX_NUM) return res;
            }
        }
    } else {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) res = Math.max(res, nums[i] ^ nums[j]);
        }
    }

    return res;
};

4、复杂度​

  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png

· 阅读需 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