题目描述

在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。

对于给定的查询单词 query，拼写检查器将会处理两类拼写错误：

• 大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。

  • 例如：wordlist = ["yellow"], query = "YellOw": correct = "yellow"
  • 例如：wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
  • 例如：wordlist = ["yellow"], query = "yellow": correct = "yellow"

• 元音错误：如果在将查询单词中的元音（‘a’、‘e’、‘i’、‘o’、‘u’）分别替换为任何元音后，能与单词列表中的单词匹配（不区分大小写），则返回的正确单词与单词列表中的匹配项大小写相同。

  • 例如：wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
  • 例如：wordlist = ["YellOw"], query = "yeellow": correct = "" （无匹配项）
  • 例如：wordlist = ["YellOw"], query = "yllw": correct = "" （无匹配项）

此外，拼写检查器还按照以下优先级规则操作：

• 当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
• 当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
• 当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
• 如果该查询在单词列表中没有匹配项，则应返回空字符串。

给出一些查询 queries，返回一个单词答案列表 answer，其中 answer[i] 是由查询 query = queries[i] 得到的正确单词。

样例

输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

注意

• 1 <= wordlist.length <= 5000
• 1 <= queries.length <= 5000
• 1 <= wordlist[i].length <= 7
• 1 <= queries[i].length <= 7
• wordlist 和 queries 中的所有字符串仅由英文字母组成。

算法1

(暴力枚举) $O(nmL)$

• 对于每个询问的单词，都去单词列表中逐一检查是否符合条件。

时间复杂度

• 每次需要 $O(mL)$ 的时间去判定，$L$ 为单词的平均长度，故总时间复杂度为 $O(nmL)$。

C++ 代码

class Solution {
public:

    bool match(const string &x, const vector<string> &wordlist) {
        int n = wordlist.size();
        for (int i = 0; i < n; i++)
            if (x == wordlist[i])
                return true;
        return false;
    }

    int caseMatch(const string &x, const vector<string> &wordlist) {
        int n = wordlist.size();
        for (int i = 0; i < n; i++) {
            if (x.length() != wordlist[i].length())
                continue;
            bool flag = true;
            for (int j = 0; j < x.length(); j++) {
                char c1 = x[j], c2 = wordlist[i][j];
                if (x[j] >= 'A' && x[j] <= 'Z')
                    c1 = x[j] - 'A' + 'a';
                if (wordlist[i][j] >= 'A' && wordlist[i][j] <= 'Z')
                    c2 = wordlist[i][j] - 'A' + 'a';
                if (c1 != c2) {
                    flag = false;
                    break;
                }
            }

            if (flag)
                return i;
        }
        return -1;
    }

    int vowelMatch(const string &x, const vector<string> &wordlist) {
        int n = wordlist.size();
        for (int i = 0; i < n; i++) {
            if (x.length() != wordlist[i].length())
                continue;
            bool flag = true;
            for (int j = 0; j < x.length(); j++) {
                char c1 = x[j], c2 = wordlist[i][j];
                if (x[j] >= 'A' && x[j] <= 'Z')
                    c1 = x[j] - 'A' + 'a';
                if (wordlist[i][j] >= 'A' && wordlist[i][j] <= 'Z')
                    c2 = wordlist[i][j] - 'A' + 'a';
                if (c1 != c2) {
                    if (!((c1 == 'a' || c1 == 'e' || c1 == 'i' || c1 == 'o' || c1 == 'u')
                     && (c2 == 'a' || c2 == 'e' || c2 == 'i' || c2 == 'o' || c2 == 'u'))) {
                         flag = false;
                         break;
                    }
                }
            }

            if (flag)
                return i;
        }
        return -1;
    }

    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        int n = queries.size();
        vector<string> ans(n, "");

        for (int i = 0; i < n; i++) {
            int j;
            if (match(queries[i], wordlist)) {
                ans[i] = queries[i];
            }
            else if ((j = caseMatch(queries[i], wordlist)) != -1) {
                ans[i] = wordlist[j];
            }
            else if ((j = vowelMatch(queries[i], wordlist)) != -1) {
                ans[i] = wordlist[j];
            }
        }
        return ans;
    }
};

算法2

(哈希表) $O(nL)$

1. 建立三个哈希表，第一个为原始字符串的集合；第二个为不区分大小写后的一个映射，由字符串映射到原始字符串数组中的下标；第三个为不区分元音和大小写后的一个映射，由字符串映射到原始字符串数组中的下标，只需要把所有元音字符换成 * 即可。
2. 查询时，依次查询三个哈希表即可。

时间复杂度

• 哈希表的操作时间复杂度为常数，每次需要 $O(L)$ 的时间来操作字符串，故时间复杂度为 $O(nL)$。

C++ 代码

class Solution {
public:

    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        int n = queries.size(), m = wordlist.size();
        unordered_set<string> h1;
        unordered_map<string, int> h2;
        unordered_map<string, int> h3;

        vector<string> ans(n, "");

        for (int i = 0; i < m; i++) {
            h1.insert(wordlist[i]);
            string str = wordlist[i];
            for (int j = 0; j < str.length(); j++)
                if (str[j] >= 'A' && str[j] <= 'Z')
                    str[j] = str[j] - 'A' + 'a';
            if (h2.find(str) == h2.end()) 
                h2[str] = i;

            for (int j = 0; j < str.length(); j++)
                if (str[j] == 'a' || str[j] == 'e' || str[j] == 'i' || str[j] == 'o' || str[j] == 'u')
                    str[j] = '*';

            if (h3.find(str) == h3.end()) 
                h3[str] = i;
        }

        for (int i = 0; i < n; i++) {
            if (h1.find(queries[i]) != h1.end())
                ans[i] = queries[i];
            else {
                string str = queries[i];
                for (int j = 0; j < str.length(); j++)
                    if (str[j] >= 'A' && str[j] <= 'Z')
                        str[j] = str[j] - 'A' + 'a';
                if (h2.find(str) != h2.end())
                    ans[i] = wordlist[h2[str]];
                else {
                    for (int j = 0; j < str.length(); j++)
                        if (str[j] == 'a' || str[j] == 'e' || str[j] == 'i' || str[j] == 'o' || str[j] == 'u')
                            str[j] = '*';
                    if (h3.find(str) != h3.end()) 
                        ans[i] = wordlist[h3[str]];
                }
            }
        }
        return ans;
    }
};