LeetCode 249 - Group Shifted Strings

作者 QIFAN 日期 2017-02-08
LeetCode 249 - Group Shifted Strings

原题链接(锁):249. Group Shifted Strings


题干

一个字符串可以通过 shift 变成另一个字符串,比如 ‘abc’ –> ‘bcd’ (所有字母右移一位),把可通过 shift 转换的字符串看成同组。给定一个 String 数组,将其分组并返回结果。

思路

使用 HashMap<String, ArrayList<String>> 存以 a 开头的字符串,遍历数组,先把每个字符串转成以 a 开头的,存到相应 key 。
注意 shift 时 转换后字母 = ‘a’ +(转换前字母 - shift 长度 + 26 - ‘a’)% 26, shift 长度 = s.charAt(0) - ‘a’

时间复杂度 $O(N)$

代码:

public List<List<String>> groupStrings(String[] strings) {
List<List<String>> res = new ArrayList<>();
if (strings == null || strings.length == 0) {
return res;
}
HashMap<String, List<String>> map = new HashMap<>();
for (String s: strings) {
String reset = resetString(s);
if (!map.containsKey(reset)) {
map.put(reset, new ArrayList<String>());
}
map.get(reset).add(s);
}
for(Map.Entry<String, List<String>> entry: map.entrySet()) {
res.add(entry.getValue());
}
return res;
}
private String resetString(String s) {
if (s.length() == 0) {
return s;
}
StringBuilder sb = new StringBuilder();
int shiftLength = s.charAt(0) - 'a';
for (int i = 0; i < s.length(); i++) {
int shifted = 'a' + (s.charAt(i) - shiftLength + 26 - 'a') % 26;
sb.append((char)shifted);
}
// System.out.println(sb.toString());
return sb.toString();
}