Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

1
"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],

A solution is:

1
2
3
4
5
6
[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

很简单的一个题目。

  1. 要想把同一类型的字符串归类，要选择一种变形方式，让所有同类型的字符串能变形成为同一个字符串
  2. 然后以这个字符串做为HashMap的Key，来归类字符串
  3. 我选择的方式，字符串中所有的字符，减去第一个字符。所有字符向0看齐
  4. 有一点需要注意的是，”ba” 这种字符串，后面的字符有的比第一个小，减完之后是负数，这时候就要加上一个26.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<String>> groupStrings(String[] strings) {
    HashMap<String, List<String>> map = new HashMap<>();
    for (String str : strings) {
        char[] chars = str.toCharArray();
        char first = chars[0];
        for (int i = 0; i < chars.length; i++) {
            chars[i] = (char) (chars[i] >= first ? chars[i] - first : chars[i] - first + 26);
        }
        String key = new String(chars);
        if (map.containsKey(key)) {
            map.get(key).add(str);
        } else {
            map.put(key, new ArrayList<String>());
            map.get(key).add(str);
        }
    }
    return new ArrayList<List<String>>(map.values());
}