An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:
a) it --> it (no abbreviation) 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
Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.
Example:
Given dictionary = [ "deer", "door", "cake", "card" ] isUnique("dear") ->Solution 1: Use HashMapfalse
isUnique("cart") ->true
isUnique("cane") ->false
isUnique("make") ->true
public class ValidWordAbbr {
Map<String,Set<String>> map=new HashMap<>();
public ValidWordAbbr(String[] dictionary) {
for (String s: dictionary) {
String key=genShort(s);
if (map.containsKey(key)) map.get(key).add(s);
else {
Set<String> one=new HashSet<>();
one.add(s);
map.put(key,one);
}
}
}
public boolean isUnique(String word) {
String key=genShort(word);
if (!map.containsKey(key)) return true;
if (map.get(key).size()>1) return false;
if (map.get(key).contains(word)) return true;
return false;
}
private String genShort(String s) {
if (s.length()<=2) return s;
StringBuilder sb=new StringBuilder();
sb.append(s.charAt(0));
sb.append(String.valueOf(s.length()-2));
sb.append(s.charAt(s.length()-1));
return sb.toString();
}
}
Solution 2: Do not really need to use Set<String>, can be slightly faster. public class ValidWordAbbr {
Map<String,String> map=new HashMap<>();
public ValidWordAbbr(String[] dictionary) {
for (String s: dictionary) {
String key=genShort(s);
if (map.containsKey(key)) {
if (s.equals(map.get(key))) continue;
map.put(key,"");
}
else map.put(key,s);
}
}
public boolean isUnique(String word) {
String key=genShort(word);
if (!map.containsKey(key)) return true;
return word.equals(map.get(key));
}
private String genShort(String s) {
if (s.length()<=2) return s;
StringBuilder sb=new StringBuilder();
sb.append(s.charAt(0));
sb.append(String.valueOf(s.length()-2));
sb.append(s.charAt(s.length()-1));
return sb.toString();
}
}
没有评论:
发表评论