249. Group Shifted Strings

发表于 | 分类于

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： HashMap

基本的思路是要构造一个hash function，使得属于一个sequence的字符串可以group到一起。一个思路是把每一个字符转换成对于与第一个字符的位置。
这里要处理的是负数的情况，比如ba,az，这里用到的trick是用(diff + 26) % 26 来转换成正整数。
同时要注意的是需要分隔开不同的数字，因为对于012不能区分是0-12还是0-1-2.

lang: 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
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<>();
        if (strings == null || strings.length == 0) {
            return res;
        }
        // Design a hash function
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strings) {
            // construct the hash key
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < str.length(); i++) {
                sb.append(Integer.toString((str.charAt(i) - str.charAt(0) + 26) % 26));
                sb.append(".");
            }
            String key = sb.toString();
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<String>());
            }
            map.get(key).add(str);
        }
        for (String key : map.keySet()) {
            res.add(map.get(key));
        }
        return res;
    }
}