676.实现一个魔法字典

2022-08-30 | 2023-12-21 | 530 | 2 分钟

实现一个魔法字典

字典树

解题思路：
- 使用第一种方法比较两个字符串时，首先需要保证它们的长度相等；
- 随后遍历这两个字符串，需要保证这两个字符串恰好有一个位置对应的字符不同；
复杂度：
- 时间复杂度： O(qnl)，其中 n 是数组 dictionary 的长度，l 是数组 dictionary 中字符串的平均长度，q 是函数 search(searchWord) 的调用次数；
- 空间复杂度：O(nl)，即数组需要使用的空间；

代码实现：

class MagicDictionary {
    words: Array<string>
    constructor() {
        this.words = [];
    }

    buildDict(dictionary: string[]): void {
        this.words = dictionary;
    }

    search(searchWord: string): boolean {
        for (const word of this.words) {
            if (word.length !== searchWord.length) {
                continue;
            }

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

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

哈希

解题思路：
- 将长度相同的放入到同一个 hash 中；
- 然后搜索的时候遍历对应长度的数组，找到满足的单词；
复杂度：
- 时间复杂度：O(kS)，S 为所有输入单词的字符数，K 为目标词的长度；
  - buidDict 遍历词组计算词长需要 O(S)；
  - search 时候如果字典所有单词与目标词长度一致最差需要 O(kS)；
  - Search 最好达到 O(1)；
- 空间复杂度：O(S)，S 为所有输入单词的字符数；

代码实现：

class MagicDictionary {
    map: Map<number, Array<string>>

    constructor() {
        this.map = new Map<number, Array<string>>()
    }

    buildDict(dictionary: string[]): void {
        for (const word of dictionary) {
            let list: Array<string>
            if (this.map.has(word.length)) {
                list = this.map.get(word.length)
            } else {
                list = new Array<string>()
            }
            list.push(word)
            this.map.set(word.length, list)
        }
    }

    search(searchWord: string): boolean {
        if (this.map.has(searchWord.length)) {
            out:
            for (const word of this.map.get(searchWord.length)) {
                let cnt = 0
                for (let i = 0; i < word.length; i++) {
                    // 字符不相等并且超过 1 个字符，直接跳出返回 false
                    if (searchWord.charCodeAt(i) !== word.charCodeAt(i) && ++cnt > 1) {
                        continue out
                    }
                }
                if (cnt == 1) {
                    return true
                }
            }
        }
        return false
    }
}

打赏作者

您的打赏是我前进的动力

微信

支付宝

第 1️⃣ 座大山：Let、const、var 的区别

剑指 Offer 30.包含min函数的栈

中午好👏🏻，我是 ✍🏻 疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

1. 实现一个魔法字典
2. 字典树
3. 哈希