> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/string/group-shifted-strings.md).

# Group Shifted Strings

<https://leetcode.com/problems/group-shifted-strings/description/>

> 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"],
>
> A solution is:
>
> \[
>
> \["abc","bcd","xyz"],
>
> \["az","ba"],
>
> \["acef"],
>
> \["a","z"]
>
> ]

## Thoughts

字符之间间隔存在规律, 统计出来作为key就好了. 由于是circular的, 当str\[i] < str\[i - 1]时直接加26.

## Code

```
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<>();
        Map<String, List<String>> rules = new HashMap<>();
        for (String str : strings) {
            StringBuilder key = new StringBuilder();
            for (int i = 1; i < str.length(); i++) {
                int x = str.charAt(i) - str.charAt(i - 1);
                key.append(str.charAt(i) < str.charAt(i - 1) ? x + 26 : x);
            }
            if (!rules.containsKey(key.toString())) {
                rules.put(key.toString(), new ArrayList<>());
            }
            rules.get(key.toString()).add(str);
        }

        for (String key : rules.keySet()) {
            res.add(rules.get(key));
        }

        return res;
    }
}
```

## Analysis

时间复杂度O(MN). M为单词长度.