# 249.Group Shifted Strings

[Link](https://medium.com/leetcode-%E6%BC%94%E7%AE%97%E6%B3%95%E6%95%99%E5%AD%B8/017-leetcode-249%E6%BC%94%E7%AE%97%E6%B3%95-group-shifted-strings-%E7%BE%A4%E7%B5%84%E5%81%8F%E7%A7%BB%E5%AD%97%E4%B8%B2-c8fa3aeb5548)

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.

**Solution**

1. 先把規律找出來 -> 規律當作hashMap的key
2. 將同個規律的放到一組，同個key下的value
3. 最後把value都進過lexicographic 排序過 並output

```
public static List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> map = new HashMap<>();
        for(int i = 0; i < strings.length ; i++){
            String key = getShiftedRelation(strings[i]);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(strings[i]);
            map.put(key, list);
        }
        List<List<String>> ret = new ArrayList<>();
        for (List list: map.values()) {
            Collections.sort(list);
            ret.add(list);
        }
        return ret;
    }

    private static String getShiftedRelation(String string) {
        String ret = "";
        for(int i = 1; i < string.length(); i++){
            int diff = string.charAt(i) - string.charAt(i-1);
            diff = diff < 0 ? diff+26 : diff;
            ret += diff +",";
        }
        return ret;
    }
```
