# 249 Group Shifted Strings

## 249. [Group Shifted Strings](https://leetcode.com/problems/group-shifted-strings/description/)

## 1. Question

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"]
]
```

## 2. Implementation

**(1) HashMap**

思路: 这里比较巧妙的做法是根据每个词的character和它之前的character的偏移量作为key. 注意由于a - z = -25, 为了让计算的结果统一为正数，我们需要对结果 + 26 再 模26

```java
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<>();

        if (strings == null || strings.length == 0) {
            return res;
        }

        Map<String, List<String>> map = new HashMap<>();

        for (String str : strings) {
            StringBuilder key = new StringBuilder();

            for (int i = 1; i < str.length(); i++) {
                int offset = (str.charAt(i) - str.charAt(i - 1) + 26) % 26;
                key.append(offset);
            }

            String k = key.toString();
            if (!map.containsKey(k)) {
                map.put(k, new LinkedList<>());
            }
            map.get(k).add(str);
        }
        res = new ArrayList<>(map.values());
        return res;
    }
}
```

## 3. Time & Space Complexity

**HashMap:** 时间复杂度O(nL), 空间复杂度O(n)


---

# 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://protegejj.gitbook.io/algorithm-practice/google/249-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.