Question

Formatted question description: https://leetcode.ca/all/288.html

 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

 @tag-design

Algorithm

Code

Java

  • import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Set;
    
    public class Unique_Word_Abbreviation {
    
        /*
            more test cases
    
            1. dictionary = {"dear"},  isUnique("door") -> false
    
            2. dictionary = {"door", "door"}, isUnique("door") -> true
    
            3. dictionary = {"dear", "door"}, isUnique("door") -> false
    
         */
        public static void main(String[] args) {
            Unique_Word_Abbreviation out = new Unique_Word_Abbreviation();
            ValidWordAbbr s = out.new ValidWordAbbr(new String[]{"deer", "door", "cake", "card"});
    
            System.out.println(s.isUnique("cart"));
        }
    
        public class ValidWordAbbr {
    
            Map<String, Set<String>> map;
    
            public boolean isUnique(String word) {
                String abbr = getAbbr(word);
                // @note: same word, and only this same word
                if (!map.containsKey(abbr) || (map.get(abbr).contains(word) && map.get(abbr).size() == 1)) {
                    return true;
                }
    
                return false;
            }
    
            public ValidWordAbbr(String[] dictionary) {
                map = new HashMap<>();
                for (String s : dictionary) {
                    String abbr = getAbbr(s);
                    if (!map.containsKey(abbr)) {
                        map.put(abbr, new HashSet<String>());
                    }
                    map.get(abbr).add(s);
                }
            }
    
            private String getAbbr(String s) {
                if (s.length() < 3) {
                    return s;
                }
                int len = s.length();
    
                return s.substring(0, 1) + (len - 2) + s.substring(len - 1);
            }
        }
    }
    
  • Todo
    
  • class ValidWordAbbr(object):
      def __init__(self, dictionary):
        """
        initialize your data structure here.
        :type dictionary: List[str]
        """
        self.d = {}
        self.dict = dictionary = set(dictionary)
        for word in dictionary:
          wordLen = len(word)
          if wordLen > 2:
            key = word[0] + str(wordLen - 2) + word[-1]
            self.d[key] = self.d.get(key, 0) + 1
          else:
            self.d[word] = self.d.get(word, 0) + 1
    
      def isUnique(self, word):
        """
        check if a word is unique.
        :type word: str
        :rtype: bool
        """
        wordLen = len(word)
        key = None
        if wordLen > 2:
          key = word[0] + str(wordLen - 2) + word[-1]
        else:
          key = word
        if key in self.d:
          if self.d[key] == 1 and word in self.dict:
            return True
          return False
        else:
          return True
    
    # Your ValidWordAbbr object will be instantiated and called as such:
    # vwa = ValidWordAbbr(dictionary)
    # vwa.isUnique("word")
    # vwa.isUnique("anotherWord")
    
    

All Problems

All Solutions