# 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为单词长度.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/string/group-shifted-strings.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.