2015年11月5日星期四

Leetcode 288 Unique Word Abbreviation

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") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true
Solution 1: Use HashMap
 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();  
   }  
 }  

没有评论:

发表评论