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")