Group Shifted Strings

Total Accepted: 8470 Total Submissions: 27003 Difficulty: Easy
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.

思路

• 参考
• 用一个hashtable去存string pattern,这个string pattern作为key,然后他对应的strings们作为value
• 怎么去找这个string pattern呢?
• 可以有很多方法,比如找string里边跟第一个字母的距离,或者每个字符的距离
• 还有一个容易错的地方,就是遇到超出了z之后又重头开始的情况,比如yza
• 这个时候,可以((a - y) + 26) % 26
• ["eqdf", "qcpr"]
• 同时两个字符相减可能为两位数,所以用一个字符隔开,否则121的pattern 也有可能是1 21
• ((‘q’ - 'e') + 26) % 26 = 12, ((‘d’ - 'q') + 26) % 26 = 13, ((‘f’ - 'd') + 26) % 26 = 2
• ((‘c’ - 'q') + 26) % 26 = 12, ((‘p’ - 'c') + 26) % 26 = 13, ((‘r’ - 'p') + 26) % 26 = 2

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<List<String>>();
        HashMap<String, List<String>> d = new HashMap<>();
        for(int i = 0; i < strings.length; i++) {
            StringBuffer sb = new StringBuffer();
            for(int j = 0; j < strings[i].length(); j++) {
                sb.append(Integer.toString(((strings[i].charAt(j) - strings[i].charAt(0)) + 26) % 26));
                sb.append(" ");
            }
            String shift = sb.toString();
            if(d.containsKey(shift)) {
                d.get(shift).add(strings[i]);
            } else {
                List<String> l = new ArrayList<>();
                l.add(strings[i]);
                d.put(shift, l);
            }
        }

        for(String s : d.keySet()) {
            Collections.sort(d.get(s));
            result.add(d.get(s));
        }
        return result;
    }
}