leetcode
leetcode 251 ~ 300
单词的唯一缩写

单词的唯一缩写

难度:

标签:

题目描述

代码结果

运行时间: 67 ms, 内存: 26.0 MB


/*
 * 思路:
 * 1. 对于给定的字符串列表,生成每个字符串的唯一缩写。
 * 2. 缩写的规则是:第一个字符 + 中间字符数 + 最后一个字符。例如,"internationalization" -> "i18n"。
 * 3. 对于每个字符串,检查其缩写是否唯一。如果多个字符串的缩写相同,需要保留其原始形式。
 */
 
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
 
public class UniqueWordAbbreviationStream {
    private Map<String, String> abbreviationMap;
 
    public UniqueWordAbbreviationStream(String[] dictionary) {
        abbreviationMap = Arrays.stream(dictionary)
            .collect(Collectors.toMap(
                this::getAbbreviation,
                Function.identity(),
                (existing, replacement) -> existing.equals(replacement) ? existing : ""
            ));
    }
 
    public boolean isUnique(String word) {
        String abbr = getAbbreviation(word);
        return !abbreviationMap.containsKey(abbr) || abbreviationMap.get(abbr).equals(word);
    }
 
    private String getAbbreviation(String word) {
        if (word.length() <= 2) return word;
        return word.charAt(0) + String.valueOf(word.length() - 2) + word.charAt(word.length() - 1);
    }
}
 

解释

方法:

该题解的思路是将单词转换为唯一缩写形式作为哈希表的键,将原单词存储在对应的值列表中。对于查询单词,先计算其唯一缩写,然后在哈希表中查找对应的值列表。如果列表长度为1且与查询单词相同,则认为该单词的缩写是唯一的;如果列表长度大于1或者列表中的单词与查询单词不同,则认为该单词的缩写不唯一。对于长度小于等于2的单词,直接认为其缩写是唯一的。

时间复杂度:

构造函数: O(n), isUnique 函数: 平均 O(1),最坏 O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择单词的首尾字符和长度作为缩写的策略?这种策略是否在某些特定情况下会导致高冲突率?
选择单词的首尾字符和长度作为缩写的策略是因为这样简洁且通常能保持单词的唯一性,同时减少存储空间的需求。然而,这种策略在某些情况下会导致高冲突率,尤其是在单词长度相同且首尾字符也相同的情况下。例如,单词'banner'和'boomer'都将缩写为'b4r',这会导致冲突。
🦆
在`__init__`函数中,对于长度小于等于2的单词,直接使用单词本身作为键值而非其缩写形式,这种处理方式的理由是什么?
对于长度小于等于2的单词,其缩写形式(如果按照首尾字符和中间字符数量来定义)实际上与原单词相同,因此使用单词本身作为键值可以简化处理流程,并且在这种情况下,单词本身就是其唯一的标识,不需要再进行缩写。
🦆
在`isUnique`函数中,当哈希表中不存在查询单词的唯一缩写键时,直接返回True认为缩写是唯一的,这种假设是否总是安全的?
当哈希表中不存在查询单词的唯一缩写键时,直接返回True通常是安全的,因为这意味着在初始化字典时没有任何其他单词具有相同的缩写形式。然而,这种假设的前提是所有可能影响结果的单词都已经在初始化时被考虑了。如果字典在之后被修改,或者在初始化时未包括所有相关单词,则这种假设可能不安全。
🦆
在处理对于长度大于1的单词时,如果存在多个相同的单词是否会影响哈希表的构建或查询结果的正确性?
如果存在多个相同的单词,它们会被添加到哈希表的同一键下的值列表中。这本身不会影响哈希表的构建,但会影响查询结果的正确性。在`isUnique`函数中,如果某个缩写下的单词列表包含多个相同的单词,这可能导致错误地认为这些单词的缩写不是唯一的,即使它们实际上是相同的单词。因此,处理方式应当在添加单词时检查是否已存在相同单词,以避免这种情况。

相关问题

列举单词的全部缩写

列举单词的全部缩写