1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class ValidWordAbbr {
private Map<String, String> abb;
public ValidWordAbbr(String[] dictionary) {
abb = new HashMap<>();
for (String word : dictionary) {
String currAbbrev = getAbbrev(word);
if (abb.containsKey(currAbbrev) && !abb.get(currAbbrev).equals(word)) {
abb.put(currAbbrev, "");
} else {
abb.put(currAbbrev, word);
}
}
}
public boolean isUnique(String word) {
String currAbbrev = getAbbrev(word);
return !abb.containsKey(currAbbrev) || abb.get(currAbbrev).equals(word);
}
private String getAbbrev(String word) {
if (word.length() < 3) {
return word;
}
StringBuilder abbrev = new StringBuilder();
abbrev.append(word.charAt(0)).append(word.length() - 2).append(word.charAt(word.length() - 1));
return abbrev.toString();
}
}
|
它这个意思就是给定的word的abbrev要么和dict中的每一个word都不同, 要么是和dict中abbrev相同的word, dict中每一个这样的word都和给定的word相同. 这样的话, 我们在遍历dict的时候并且把abbrev存到map中时, 一个abbrev只能对应一个word, 如果出现两个word有相同的abbrev, 那么无论isUnique给定什么word, 都不可能满足题意. 因此这种情况我们就把key, value pair变为此时的abbrev对应空string. 于是我们判断isUnique的时候先看abb是否包含当前word的abbrev, 如果不包含return true, 如果包含我们就要看对应的word是否和提供的word相同. 这里有两种情况, 要么这个abbrev对应dict中一个单独的word, 也就是key value pair中的value是个切切实实的word, 我们就比较即可. 如果当前的abbrev对应dict中多个不同的word, 那么按照我们之前的操作, 此时对应的value是个空字符串, 因此.equals的话会返回false. 满足题意.
时间复杂度: constructor是O(n * m), n是string的个数, m是string的长度. isUnique是O(n), n是word的长度.
空间复杂度: O(l) l是unique abbrev的个数.
