跳转至

966. 元音拼写检查器

题目描述

在给定单词列表 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] 得到的正确单词。

 

示例 1：

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

示例 2:

输入：wordlist = ["yellow"], queries = ["YellOw"]
输出：["yellow"]

 

提示：

  • 1 <= wordlist.length, queries.length <= 5000
  • 1 <= wordlist[i].length, queries[i].length <= 7
  • wordlist[i] 和 queries[i] 只包含英文字母

解法

方法一：哈希表

遍历 wordlist，将单词按照大小写不敏感、元音不敏感的规则分别存入哈希表 low 和 pat 中，其中 low 的键为单词的小写形式，pat 的键为将单词的元音字母替换为 * 后的字符串，值为单词本身。用哈希表 s 存储 wordlist 中的单词。

遍历 queries，对于每个单词 q，如果 q 在 s 中，说明 q 在 wordlist 中，直接将 q 加入答案数组 ans 中；否则，如果 q 的小写形式在 low 中，说明 q 在 wordlist 中，且大小写不敏感，将 low[q.lower()] 加入答案数组 ans 中；否则，如果将 q 的元音字母替换为 * 后的字符串在 pat 中，说明 q 在 wordlist 中，且元音不敏感，将 pat[f(q)] 加入答案数组 ans 中；否则，说明 q 在 wordlist 中，且大小写和元音都不敏感，将空字符串加入答案数组 ans 中。

最后返回答案数组 ans 即可。

时间复杂度 $O(n+m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别为 wordlist 和 queries 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def f(w):
            t = []
            for c in w:
                t.append("*" if c in "aeiou" else c)
            return "".join(t)

        s = set(wordlist)
        low, pat = {}, {}
        for w in wordlist:
            t = w.lower()
            low.setdefault(t, w)
            pat.setdefault(f(t), w)

        ans = []
        for q in queries:
            if q in s:
                ans.append(q)
                continue
            q = q.lower()
            if q in low:
                ans.append(low[q])
                continue
            q = f(q)
            if q in pat:
                ans.append(pat[q])
                continue
            ans.append("")
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> s = new HashSet<>();
        Map<String, String> low = new HashMap<>();
        Map<String, String> pat = new HashMap<>();
        for (String w : wordlist) {
            s.add(w);
            String t = w.toLowerCase();
            low.putIfAbsent(t, w);
            pat.putIfAbsent(f(t), w);
        }
        int m = queries.length;
        String[] ans = new String[m];
        for (int i = 0; i < m; ++i) {
            String q = queries[i];
            if (s.contains(q)) {
                ans[i] = q;
                continue;
            }
            q = q.toLowerCase();
            if (low.containsKey(q)) {
                ans[i] = low.get(q);
                continue;
            }
            q = f(q);
            if (pat.containsKey(q)) {
                ans[i] = pat.get(q);
                continue;
            }
            ans[i] = "";
        }
        return ans;
    }

    private String f(String w) {
        char[] cs = w.toCharArray();
        for (int i = 0; i < cs.length; ++i) {
            char c = cs[i];
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                cs[i] = '*';
            }
        }
        return String.valueOf(cs);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> s(wordlist.begin(), wordlist.end());
        unordered_map<string, string> low;
        unordered_map<string, string> pat;
        auto f = [](string& w) {
            string res;
            for (char& c : w) {
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                    res += '*';
                } else {
                    res += c;
                }
            }
            return res;
        };
        for (auto& w : wordlist) {
            string t = w;
            transform(t.begin(), t.end(), t.begin(), ::tolower);
            if (!low.count(t)) {
                low[t] = w;
            }
            t = f(t);
            if (!pat.count(t)) {
                pat[t] = w;
            }
        }
        vector<string> ans;
        for (auto& q : queries) {
            if (s.count(q)) {
                ans.emplace_back(q);
                continue;
            }
            transform(q.begin(), q.end(), q.begin(), ::tolower);
            if (low.count(q)) {
                ans.emplace_back(low[q]);
                continue;
            }
            q = f(q);
            if (pat.count(q)) {
                ans.emplace_back(pat[q]);
                continue;
            }
            ans.emplace_back("");
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func spellchecker(wordlist []string, queries []string) (ans []string) {
    s := map[string]bool{}
    low := map[string]string{}
    pat := map[string]string{}
    f := func(w string) string {
        res := []byte(w)
        for i := range res {
            if res[i] == 'a' || res[i] == 'e' || res[i] == 'i' || res[i] == 'o' || res[i] == 'u' {
                res[i] = '*'
            }
        }
        return string(res)
    }
    for _, w := range wordlist {
        s[w] = true
        t := strings.ToLower(w)
        if _, ok := low[t]; !ok {
            low[t] = w
        }
        if _, ok := pat[f(t)]; !ok {
            pat[f(t)] = w
        }
    }
    for _, q := range queries {
        if s[q] {
            ans = append(ans, q)
            continue
        }
        q = strings.ToLower(q)
        if s, ok := low[q]; ok {
            ans = append(ans, s)
            continue
        }
        q = f(q)
        if s, ok := pat[q]; ok {
            ans = append(ans, s)
            continue
        }
        ans = append(ans, "")
    }
    return
}

评论