元音拼写检查器
难度:
标签:
题目描述
代码结果
运行时间: 68 ms, 内存: 18.8 MB
/*
题目思路:
1. 使用流式操作处理数据。
2. 创建一个直接匹配的Set和两个用于不区分大小写匹配和元音错误匹配的Map。
3. 对每个查询进行流式处理,按照优先级返回结果。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class SpellCheckerStream {
private Set<String> wordSet;
private Map<String, String> caseInsensitiveMap;
private Map<String, String> vowelErrorMap;
private static final String VOWELS = "aeiou";
public SpellCheckerStream(String[] wordlist) {
wordSet = Stream.of(wordlist).collect(Collectors.toSet());
caseInsensitiveMap = Stream.of(wordlist).collect(Collectors.toMap(String::toLowerCase, word -> word, (a, b) -> a));
vowelErrorMap = Stream.of(wordlist).collect(Collectors.toMap(word -> deVowel(word.toLowerCase()), word -> word, (a, b) -> a));
}
public String[] spellcheck(String[] queries) {
return Stream.of(queries)
.map(this::correctWord)
.toArray(String[]::new);
}
private String correctWord(String query) {
if (wordSet.contains(query)) {
return query;
}
String lowerQuery = query.toLowerCase();
if (caseInsensitiveMap.containsKey(lowerQuery)) {
return caseInsensitiveMap.get(lowerQuery);
}
String deVowelQuery = deVowel(lowerQuery);
return vowelErrorMap.getOrDefault(deVowelQuery, "");
}
private String deVowel(String word) {
return word.replaceAll("[aeiou]", "*");
}
public static void main(String[] args) {
String[] wordlist = {"KiTe","kite","hare","Hare"};
String[] queries = {"kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"};
SpellCheckerStream checker = new SpellCheckerStream(wordlist);
System.out.println(Arrays.toString(checker.spellcheck(queries)));
}
}
解释
方法:
该题解利用了哈希表来优化拼写检查器的查询速度。首先,创建了三种映射:
1. 原始单词列表的集合's',用于检查完全匹配的情况(区分大小写)。
2. 'low'哈希表,将单词列表中的每个单词转换为小写,并存储第一个出现的单词,用于处理大小写错误。
3. 'pat'哈希表,使用一个辅助函数f将单词中的元音替换为'*',然后转为小写,这样可以处理元音错误的情况。
对于每个查询,程序首先检查完全匹配,然后是大小写错误,接着是元音错误,如果都不匹配,则返回空字符串。
时间复杂度:
O(n*k + m)
空间复杂度:
O(n)
代码细节讲解
🦆
在处理大小写错误时,你是如何确保返回的是单词列表中第一次出现的单词版本?
▷🦆
为什么选择将元音替换为特定字符'*',而不是选择其他字符或直接删除元音?
▷🦆
在哈希表`pat`中,如果有多个不同的单词通过元音替换后得到了相同的模式,你是如何处理这种冲突的?
▷🦆
给定的算法在处理一个非常长的单词列表时是否仍能保持高效?有没有可能出现内存不足的情况?
▷