leetcode
leetcode 851 ~ 900
元音拼写检查器

元音拼写检查器

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在处理大小写错误时,你是如何确保返回的是单词列表中第一次出现的单词版本?
在创建哈希表`low`时,对于每个转换为小写的单词,我使用了`setdefault`方法。这个方法会检查哈希表中是否已经存在该键(小写单词),如果不存在,它会将键和对应的原始单词存入哈希表。因此,第一次遇到的单词版本会被存储,并在后续的查询中被返回,即使后面有相同的小写单词出现,它们也不会覆盖已存储的值。
🦆
为什么选择将元音替换为特定字符'*',而不是选择其他字符或直接删除元音?
将元音替换为特定字符'*'而不是删除,是为了保留单词的长度和结构,使得替换后的模式能更好地代表原单词的结构特征,从而更有效地处理元音错误。选择'*'作为替代字符是因为它不太可能在正常的单词中出现,从而避免混淆。使用其他字符亦可,但关键是要保证该字符在一般文本中不常见。
🦆
在哈希表`pat`中,如果有多个不同的单词通过元音替换后得到了相同的模式,你是如何处理这种冲突的?
在构建哈希表`pat`时,我同样使用了`setdefault`方法。这意味着如果多个不同的单词在元音替换后形成了相同的模式,哈希表中只会保留第一次遇到的单词。这种方法确保了查询结果的一致性,即使存在多个可能的匹配项,也总是返回列表中最先出现的那个单词。
🦆
给定的算法在处理一个非常长的单词列表时是否仍能保持高效?有没有可能出现内存不足的情况?
该算法主要依赖于哈希表来存储数据,其查询和更新操作的时间复杂度通常为O(1)。因此,算法在处理大规模数据时在时间效率上表现良好。然而,如果单词列表极长,可能会造成哈希表占用大量内存。特别是对于`pat`哈希表,如果单词列表中的单词变化多样,替换元音后的模式数量也会很大,可能导致内存使用增加。在极端情况下,这可能导致内存不足,特别是在内存有限的环境中。

相关问题