单词缩写集 · word abbreviation set

时间:2022-07-20 06:24:16

[抄题]:

一个单词的缩写根据以下的形式。下面是一些缩写的例子

a) it                      --> it    (没有缩写)

1
b) d|o|g --> d1g

1 1 1
1---5----0----5--8
c) i|nternationalizatio|n --> i18n

1
1---5----0
d) l|ocalizatio|n --> l10n

假设你有一个字典和给你一个单词,判断这个单词的缩写在字典中是否是唯一的。当字典中的其他单词的缩写均与它不同的时候, 这个单词的缩写是唯一的.

 [暴力解法]:

1把缩写全部存一遍,再一个个搜索是否为重复,不重复unique

时间分析:

空间分析:

[思维问题]:

2有单词重复但是缩写相同的情况,此时仍为unique。

但是分类讨论也不好,把两种unique合并:单词出现次数和缩写出现次数相同

[一句话思路]:

把原单词和缩写分别放在两张哈希表来查,不要一起查。

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

[一刷]:

  1. 要把字符串拼起来时,直接用+即可。取出字母用的是charAt(i)的方法
  2. hash用getOrDefault(d, 0)+1来存数,记得加括号写0

[二刷]:

[三刷]:

[四刷]:

[五刷]:

  [五分钟肉眼debug的结果]:

[总结]:

  1. 返回单词可以用"" +的形式来直接拼接

[复杂度]:Time complexity: O(n) Space complexity: O(n)

[英文数据结构或算法,为什么不用别的数据结构或算法]:

hashmap:单词+出现次数,重要的是单词。用两个来比较出现的次数是否相同。

[其他解法]:

[Follow Up]:

[LC给出的题目变变变]:

很多abbreviation的题。应该都是单独分离一个abbr函数,再用“”空格来拼接

 [代码风格] :

  1. 整体的结构是类中包括成员变量+多个方法,不要把成员变量写在某一个方法里
单词缩写集 · word abbreviation set单词缩写集 · word abbreviation set
public class ValidWordAbbr {
/*
* @param dictionary: a list of words
*/
HashMap
<String, Integer> dict = new HashMap<>();
HashMap
<String, Integer> abbr = new HashMap<>();

public ValidWordAbbr(String[] dictionary) {
for (String d : dictionary) {
dict.put(d, dict.getOrDefault(d,
0) + 1);//
}
for (String d : dictionary) {
abbr.put(getAbbr(d), abbr.getOrDefault(getAbbr(d),
0) + 1);
}
}

/*
* @param word: a string
* @return: true if its abbreviation is unique or false
*/
public boolean isUnique(String word) {
return (dict.get(word) == abbr.get(getAbbr(word)));
}

//getAbbr
private String getAbbr(String word) {
if (word.length() <= 2) {//<=
return word;//
}
return "" + word.charAt(0) + (word.length() - 2) + word.charAt(word.length() - 1);
}
}

/**
* Your ValidWordAbbr object will be instantiated and called as such:
* ValidWordAbbr obj = new ValidWordAbbr(dictionary);
* boolean param = obj.isUnique(word);
*/
View Code