Leetcode - Group Shifted String

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:

"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"],
Return:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]
Note: For the return value, each inner list's elements must follow the lexicographic order.

[分析]
思路1：第一次按长度分组，然后在第一次的各分组中按照是否属于同一shifted sequence再次分组。如何判断是否属于同一shifted sequence呢？ 两个字符串x 和 y，若对于任意i，满足y[i] - x[i] = y[0] - x[0], 注意要处理类似"az", "yx"这种情况。代码很长，实现也容易出错。
思路2：对于输入数组中的每个字符串，将其“归零”，即求出该字符串对应的shifted squence中的第一个字符串（a为起始字符）。维护一个哈希表，key为各group的“零值”，value是输入数组中属于该group的字符串。 参考https://leetcode.com/discuss/50358/my-concise-java-solution 佩服作者~

public class Solution {
    // Method 2
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> ret = new ArrayList<List<String>>();
        if (strings == null) return ret;
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        for (String s : strings) {
            int offset = s.charAt(0) - 'a';
            String key = "a";
            for (int i = 1; i < s.length(); i++) {
                char c = (char)(s.charAt(i) - offset);
                if (c < 'a')
                    c += 26;
                key += c;
            }
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<String>());
            }
            map.get(key).add(s);
        }
        for (List<String> list : map.values()) {
            Collections.sort(list);
            ret.add(list);
        }
        return ret;
    }
    // Method 1
    public List<List<String>> groupStrings1(String[] strings) {
        List<List<String>> ret = new ArrayList<List<String>>();
        if (strings == null) return ret;
        // group by length
        HashMap<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        for (String s : strings) {
            if (!map.containsKey(s.length())) {
                map.put(s.length(), new ArrayList<String>());
            }
            map.get(s.length()).add(s);
            
        }
        // in each length group, group shifted strings
        HashMap<Integer, List<String>> map2 = new HashMap<Integer, List<String>>();
        HashMap<String, List<String>> shiftedMap = new HashMap<String, List<String>>();
        for (List<String> list : map.values()) {
            int i = 0;
            while (i < list.size()) {
                String curr = list.get(i++);
                int currLen = curr.length();
                if (!map2.containsKey(currLen)) {
                    map2.put(currLen, new ArrayList<String>());
                    map2.get(currLen).add(curr);
                    shiftedMap.put(curr, new ArrayList<String>());
                    shiftedMap.get(curr).add(curr);
                } else {
                    List<String> sameLenDiffGroupBase = map2.get(currLen);
                    boolean findBuddy = false;
                    for (String base : sameLenDiffGroupBase) {
                        int diff = curr.charAt(0) - base.charAt(0);
                        if (diff < 0) diff += 26;
                        int j = 1;
                        for (; j < currLen; j++) {
                            if ((base.charAt(j) - 'a' + diff) % 26 + 'a' != curr.charAt(j))
                                break;
                        }
                        if (j == currLen) {
                            shiftedMap.get(base).add(curr); // find the group which curr belong to
                            findBuddy = true;
                            break;
                        }
                    }
                    if (!findBuddy) {//curr will start a new group
                        map2.get(currLen).add(curr);
                        shiftedMap.put(curr, new ArrayList<String>());
                        shiftedMap.get(curr).add(curr);
                    }
                        
                }
            }
        }
        // put each group in shiftedMap into result
        for (List<String> list : shiftedMap.values()) {
            Collections.sort(list);
            ret.add(list);
        }
        return ret;
    }
}