单词的唯一缩写
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
为什么选择单词的首尾字符和长度作为缩写的策略?这种策略是否在某些特定情况下会导致高冲突率?
▷🦆
在`__init__`函数中,对于长度小于等于2的单词,直接使用单词本身作为键值而非其缩写形式,这种处理方式的理由是什么?
▷🦆
在`isUnique`函数中,当哈希表中不存在查询单词的唯一缩写键时,直接返回True认为缩写是唯一的,这种假设是否总是安全的?
▷🦆
在处理对于长度大于1的单词时,如果存在多个相同的单词是否会影响哈希表的构建或查询结果的正确性?
▷