1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> map = new HashMap<>();
for (String string : strings) {
String hash = getHash(string);
map.computeIfAbsent(hash, a -> new ArrayList<>()).add(string);
}
List<List<String>> ans = new ArrayList<>(map.values());
return ans;
}
private String getHash(String s) {
StringBuilder ans = new StringBuilder();
char[] charArray = s.toCharArray();
for (int i = 1; i < charArray.length; i++) {
if (charArray[i] < charArray[i - 1]) {
ans.append(charArray[i] - charArray[i - 1] + 26).append('*');
} else {
ans.append(charArray[i] - charArray[i - 1]).append('*');
}
}
return ans.toString();
}
}
|
computeIfAbsent还挺好用. 这道题就是考察环形数组中两个元素间的距离是多少. 这里的环形数组就是26个英文字母. 我们都以顺时针为前进方向来计算距离. 注意17行和19行的‘8’是很有必要的. 因为11不能确定是三个字符两两间的距离都是1还是两个字符之间距离是11.
时间复杂度: O(n * m) n是string的个数, m是最长的string的长度. 我们遍历每一个string是O(n), 对于每个string我们要计算hash, 是O(m). 合在一起是O(m * n)
空间复杂度: O(n * m) 因为可能所有的string的hash都不相同.
