最后更新
三刷
13-Jan-2017
用“”表示出现过的单词,这样最后判断的时候就知道是不是唯一,还是压根不存在。。
public class ValidWordAbbr {
Map<String, String> map = new HashMap<>();
public ValidWordAbbr(String[] dictionary) {
if (dictionary.length == 0) return;
for (String s : dictionary) {
String abbr = genAbbr(s);
if (!map.containsKey(abbr)) {
map.put(abbr, s);
} else {
if (map.get(abbr).equals(s)) continue;
else map.put(abbr, "");
}
}
}
public boolean isUnique(String word) {
String abbr = genAbbr(word);
if (!map.containsKey(abbr)) {
return true;
} else {
return map.get(abbr).equals(word);
}
}
public String genAbbr(String s) {
int len = s.length();
if (len <= 2) return s;
return s.substring(0,1) + (len - 2) + s.substring(len-1);
}
}
二刷。
15-Nov-2016
用一刷最后说的办法,Map < String, String >, 缩写和单词的一一对应关系。
添加的时候,先缩写,如果缩写不存在就直接添加缩写和当前单词的对应关系;存在的话看看存在的是不是当前单词,不是的话就添加缩写和错误的对应关系,我用的“”作为错误,代表着当前缩写可以至少代表2个单词。
Time: O(n)添加 + O(1)缩写 + O(1)查询。
Space: O(n * 2)的map。 原来一刷是O(nk),所以第二种明显空间少。
public class ValidWordAbbr {
Map<String, String> map;
public ValidWordAbbr(String[] dictionary) {
map = new HashMap<>();
for (String s: dictionary) {
String tempStr = getAbbr(s);
if (map.containsKey(tempStr) && !map.get(tempStr).equals(s)) {
map.put(tempStr, "");
} else {
map.put(tempStr, s);
}
}
}
public String getAbbr(String word) {
if (word.length() <= 2) return word;
else return word.substring(0,1) + (word.length() - 2) + word.substring(word.length() - 1);
}
public boolean isUnique(String word) {
String s = getAbbr(word);
if (map.containsKey(s) && !map.get(s).equals(word)) {
return false;
} else {
return true;
}
}
}