-
Notifications
You must be signed in to change notification settings - Fork 88
/
UniqueWordAbbreviation288.java
97 lines (84 loc) · 2.89 KB
/
UniqueWordAbbreviation288.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
* 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
*/
public class UniqueWordAbbreviation288 {
class ValidWordAbbr {
Map<String, Set<String>> map = new HashMap<>();
public ValidWordAbbr(String[] dictionary) {
for (String word: dictionary) {
String encoded = encode(word);
if (!map.containsKey(encoded)) {
map.put(encoded, new HashSet<>());
}
map.get(encoded).add(word);
}
}
public boolean isUnique(String word) {
String encoded = encode(word);
return !map.containsKey(encoded) || (map.get(encoded).size() == 1 && map.get(encoded).contains(word));
}
private String encode(String word) {
if (word.length() <= 2) return word;
return word.charAt(0) + Integer.toString(word.length()-2) + word.charAt(word.length()-1);
}
}
/**
* https://leetcode.com/problems/unique-word-abbreviation/solution/
*/
public class ValidWordAbbr2 {
private final Map<String, Boolean> abbrDict = new HashMap<>();
private final Set<String> dict;
public ValidWordAbbr2(String[] dictionary) {
dict = new HashSet<>(Arrays.asList(dictionary));
for (String s : dict) {
String abbr = toAbbr(s);
abbrDict.put(abbr, !abbrDict.containsKey(abbr));
}
}
public boolean isUnique(String word) {
String abbr = toAbbr(word);
Boolean hasAbbr = abbrDict.get(abbr);
return hasAbbr == null || (hasAbbr && dict.contains(word));
}
private String toAbbr(String s) {
int n = s.length();
if (n <= 2) {
return s;
}
return 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);
*/
}