1.1 Unique Word Abbreviation

Description

An abbreviation of a word follows the form . 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

Method

firstly, we need a helper method to calculate the abbreviation And then the problem is to determined which means that the word is not unique.

Situation 1: There has a word in dictionary has the same abbreviation with the word, but the two words are different. - > false dear -> false;

There has a word in dictionary has the same abbreviation with the word, but the two words are same. - > true; cake -> true;

so when we do operation on dictionary, we should care about the situation of how to deal with many words have same abbreviation

if we meet a new word abbreviation we put it in map if we meet a new word that has the same abbreviation with previous word. we should look up if this word is the same with the word we put in map, if is, it fine. if not, it mean for this abbreviation, we have at least two different word, we use "" to replace the original word in map.

Time and Space Complexity

time :O(n) space : o(N)

Code

public class ValidWordAbbr {

HashMap<String, String> map;


public ValidWordAbbr(String[] dictionary) {
       map = new HashMap<>();
       if (dictionary == null || dictionary.length == 0){
           return; 
       }
       for (String str : dictionary){
            String key = getKey(str);
            if (map.containsKey(key) && !map.get(key).equals(str)){
                map.put(key, "");
            } else {
                map.put(key, str);
            }
       }
}

public boolean isUnique(String word) {
       String key = getKey(word);
       System.out.println(key);
       if (!map.containsKey(key) || map.get(key).equals(word)){
           return true;
       }
       return false;
}

private String getKey(String s){
        if (s == null || s.length() == 0){
            return "";
        }
        if (s.length() < 3){
            return s;
        }
        return new StringBuilder().append(s.charAt(0)).append(s.length() - 2).append(s.charAt(s.length() - 1)).toString();
}

}