Monday, November 7, 2016

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 



Use a set and get all abbreviations in the dict. Now for each word, check if the set contains the abbreviation.


public class ValidWordAbbr {
    private Set<string> abbreviatons;
    public ValidWordAbbr(String[] dictionary) {
        abbreviatons = new HashSet<>();
        for (String s : dictionary) {
            abbreviatons.add(getAbbreviatoin(s));
        }

    }
    public boolean isUnique(String word) {
        String abbr = getAbbreviatoin(word);
        return !abbreviatons.contains(abbr);
    }

    private String getAbbreviatoin(String s) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        StringBuilder builder = new StringBuilder();
        builder.append(s.charAt(0));
        if (len == 1) {
            return builder.toString();
        }
        if (len - 2 > 0) {
            builder.append(len - 2);
        }
        builder.append(s.charAt(len - 1));
        return builder.toString();
    }
}


No comments:

Post a Comment