966. Vowel Spellchecker

Leetcode link

题目简介

题目给我们两个参数：

• wordlist：一个字符串数组，表示我们有的字典
• queries：一个字符串数组，表示我们要用来查询字典的字符串

由于 queries 中的字符串可能会出现一些母音字母的笔误，所以我们需要设计一个算法来输出每一个查询字符串的正确字符串

输出字符串的规则如下：

1. 如果查询字符串在大小写敏感的情况下完全符合字典的某个字符串，直接返回该字符串
2. 如果查询字符串在大小写不敏感的情况下符合字典某个字符，返回字典出现的第一个对应的字符串
3. 如果查询字符串某些母音字符误写成了其他的母音字符（允许大小写不敏感），返回字典出现的第一个对应字符串
4. 如果以上都不成立，则返回空字符串

解题思路

根据上述规则，我们能很快写出一个该逻辑的算法，但是直接写出来的算法复杂度会是 $O(W \times Q \times N)$

其中 W 代表 wordlist.length，Q 代表 queries.length，N 代表所有 wordlist 字符串的平均长度

所以我们需要采取一些空间换时间的策略

这个策略分成两个部分：数据预处理、查询

数据预处理

首先为了应对第一种情况，我们可以将 wordlist 用一个 Set 保存，这种情况下我们查找任意一个 Query 的复杂度是 $O(1)$

其次为了应付第二种情况，我们可以用一个 Map 来保存所有字典字符串到全小写字典字符串的映射

第三种情况也是可以用一个 Map 来保存所有字典字符串到归一化母音字符串（把字符串中的母音字符都用一个符号代替）的映射

这个部份的时间复杂度是 $O(W \times N)$、空间复杂度是 $O(W \times N)$

查询

我们只需要遍历 queries 分别在 Set 与两个 Map 中寻找符合条件的字符就好

这个部份的时间复杂度是 $O(Q \times N)$

这样一来我们的算法时间复杂度就降低到了 $O((Q + W) \times N)$

Javascript

/**
 * @param {string[]} wordlist
 * @param {string[]} queries
 * @return {string[]}
 */
var spellchecker = function(wordlist, queries) {
    const wordSet = new Set(wordlist)
    const caseInsensitiveMap = new Map()
    const vowelInsensitiveMap = new Map()
    const res = []

    const equalizeVowels = word => word.toLowerCase().replace(/[aeiou]/g, '@')

    wordlist.forEach(word => {
        const lowerCaseWord = word.toLowerCase()
        if(!caseInsensitiveMap.has(lowerCaseWord)) {
            caseInsensitiveMap.set(lowerCaseWord, word)
        }

        const equalVowelWord = equalizeVowels(word)
        if(!vowelInsensitiveMap.has(equalVowelWord)) {
            vowelInsensitiveMap.set(equalVowelWord, word)
        }
    })

    for(const q of queries) {
        // 1. exactly match
        if(wordSet.has(q)) {
            res.push(q)
            continue
        }

        // 2. case-independant match
        const lowerCaseQuery = q.toLowerCase()
        if(caseInsensitiveMap.has(lowerCaseQuery)) {
            res.push(caseInsensitiveMap.get(lowerCaseQuery))
            continue
        }
        // 3. vowel error match
        const equalVowelQuery = equalizeVowels(q)
        if(vowelInsensitiveMap.has(equalVowelQuery)) {
            res.push(vowelInsensitiveMap.get(equalVowelQuery))
            continue
        }
        // 4. no match
        res.push('')
    }

    return res
};