-
Notifications
You must be signed in to change notification settings - Fork 45
/
_527.java
67 lines (59 loc) · 2.43 KB
/
_527.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
import java.util.*;
/**
* LeetCode 527 - Word Abbreviation
* <p>
* We first shorten each string in the most naive way.
* If more than one strings are mapped to the same key, we then extract their common prefix and recursively
* solve the problem.
*/
public class _527 {
private String shorten(String s) {
if (s.length() <= 3) return s;
else return "" + s.charAt(0) + (s.length() - 2) + s.charAt(s.length() - 1);
}
private String commonPrefix(List<String> dict, List<Integer> indices) {
String base = dict.get(indices.get(0));
for (int len = 0; len < base.length(); len++) {
for (int i = 1; i < indices.size(); i++) {
String other = dict.get(indices.get(i));
if (len >= other.length() || base.charAt(len) != other.charAt(len)) return base.substring(0, len);
}
}
return base;
}
public List<String> wordsAbbreviation(List<String> dict) {
if (dict.isEmpty()) return dict;
Map<String, List<Integer>> map = new HashMap<>();
for (int i = 0; i < dict.size(); i++) {
String key = shorten(dict.get(i));
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(i);
}
while (map.size() < dict.size()) {
Map<String, List<Integer>> map1 = new HashMap<>();
for (String key : map.keySet()) {
List<Integer> list = map.get(key);
if (list.size() > 1) {
String prefix = commonPrefix(dict, list);
for (int id : list) {
String s = dict.get(id);
String newKey = prefix + shorten(s.substring(prefix.length()));
map1.putIfAbsent(newKey, new ArrayList<>());
map1.get(newKey).add(id);
}
} else {
map1.put(key, list);
}
}
map = map1;
}
List<String> res = new ArrayList<>(dict.size());
for (int i = 0; i < dict.size(); i++) res.add(""); // place-holders
for (String s : map.keySet()) res.set(map.get(s).get(0), s);
return res;
}
public static void main(String[] args) {
_527 sol = new _527();
System.out.println(sol.wordsAbbreviation(Arrays.asList("like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion")));
}
}