Question

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

The abbreviation of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an abbreviation of itself.

For example:

dog --> d1g because there is one letter between the first letter 'd' and the last letter 'g'.
internationalization --> i18n because there are 18 letters between the first letter 'i' and the last letter 'n'.
it --> it because any word with only two characters is an abbreviation of itself.

Implement the ValidWordAbbr class:

ValidWordAbbr(String[] dictionary) Initializes the object with a dictionary of words.
boolean isUnique(string word) Returns true if either of the following conditions are met (otherwise returns false):
- There is no word in dictionary whose abbreviation is equal to word's abbreviation.
- For any word in dictionary whose abbreviation is equal to word's abbreviation, that word and word are the same.

Example 1:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

Constraints:

1 <= dictionary.length <= 3 * 10⁴
1 <= dictionary[i].length <= 20
dictionary[i] consists of lowercase English letters.
1 <= word.length <= 20
word consists of lowercase English letters.
At most 5000 calls will be made to isUnique.

Algorithm

Code

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);
        }
    }
}

############

class ValidWordAbbr {
    private Map<String, Set<String>> words;

    public ValidWordAbbr(String[] dictionary) {
        words = new HashMap<>();
        for (String word : dictionary) {
            String abbr = abbr(word);
            words.computeIfAbsent(abbr, k -> new HashSet<>()).add(word);
        }
    }

    public boolean isUnique(String word) {
        String abbr = abbr(word);
        Set<String> vals = words.get(abbr);
        return vals == null || (vals.size() == 1 && vals.contains(word));
    }

    private String abbr(String s) {
        int n = s.length();
        return n < 3 ? s : s.charAt(0) + Integer.toString(n - 2) + s.charAt(n - 1);
    }
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */

class ValidWordAbbr:
    def __init__(self, dictionary: List[str]):
        self.words = defaultdict(set)
        for word in dictionary:
            abbr = self.word_abbr(word)
            self.words[abbr].add(word)

    def isUnique(self, word: str) -> bool:
        abbr = self.word_abbr(word)
        words = self.words[abbr]
        return not words or (len(words) == 1 and word in words)

    def word_abbr(self, s):
        return s if len(s) < 3 else f'{s[0]}{len(s) - 2}{s[-1]}'


# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)

############

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

class ValidWordAbbr {
public:
    unordered_map<string, unordered_set<string>> words;

    ValidWordAbbr(vector<string>& dictionary) {
        for (auto word : dictionary) {
            auto abbr = wordAbbr(word);
            words[abbr].insert(word);
        }
    }

    bool isUnique(string word) {
        auto abbr = wordAbbr(word);
        if (!words.count(abbr)) return true;
        auto vals = words[abbr];
        return vals.size() == 1 && vals.count(word);
    }

    string wordAbbr(string s) {
        int n = s.size();
        return n < 3 ? s : s.substr(0, 1) + to_string(n - 2) + s.substr(n - 1, 1);
    }
};

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr* obj = new ValidWordAbbr(dictionary);
 * bool param_1 = obj->isUnique(word);
 */

type ValidWordAbbr struct {
	words map[string]map[string]bool
}

func Constructor(dictionary []string) ValidWordAbbr {
	words := make(map[string]map[string]bool)
	for _, word := range dictionary {
		abbr := wordAbbr(word)
		if words[abbr] == nil {
			words[abbr] = make(map[string]bool)
		}
		words[abbr][word] = true
	}
	return ValidWordAbbr{words}
}

func (this *ValidWordAbbr) IsUnique(word string) bool {
	abbr := wordAbbr(word)
	words := this.words[abbr]
	return words == nil || (len(words) == 1 && words[word])
}

func wordAbbr(s string) string {
	n := len(s)
	if n <= 2 {
		return s
	}
	return s[0:1] + strconv.Itoa(n-2) + s[n-1:]
}

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * obj := Constructor(dictionary);
 * param_1 := obj.IsUnique(word);
 */

288 - Unique Word Abbreviation

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions