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

# 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)