0288. Unique Word Abbreviation
https://leetcode.com/problems/unique-word-abbreviation
Description
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 adictionary
of words.boolean isUnique(string word)
Returnstrue
if either of the following conditions are met (otherwise returnsfalse
):There is no word in
dictionary
whose abbreviation is equal toword
's abbreviation.For any word in
dictionary
whose abbreviation is equal toword
's abbreviation, that word andword
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 * 104
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 toisUnique
.
ac1
use 2 map 1 list, time consuming
class ValidWordAbbr {
Map<Integer, Map<String, List<String>>> map;
public ValidWordAbbr(String[] dictionary) {
map = new HashMap<Integer, Map<String, List<String>>>();
for (String s : dictionary) {
int len = s.length();
String abbr = len != 0 ? s.substring(0,1) + s.substring(len-1) : "";
if (!map.containsKey(len)) map.put(len, new HashMap<String, List<String>>());
if (!map.get(len).containsKey(abbr)) map.get(len).put(abbr, new ArrayList<String>());
map.get(len).get(abbr).add(s);
}
}
public boolean isUnique(String word) {
// edge case
int len = word.length();
if (len == 0) return true;
String abbr = word.substring(0,1) + word.substring(len-1);
if (map.containsKey(len) && map.get(len).containsKey(abbr)) {
for (String s : map.get(len).get(abbr)) {
if (!word.equals(s)) return false;
}
}
return true;
}
}
/**
* Your ValidWordAbbr object will be instantiated and called as such:
* ValidWordAbbr obj = new ValidWordAbbr(dictionary);
* boolean param_1 = obj.isUnique(word);
*/
Last updated
Was this helpful?