LeetCode 249: Group Shifted Strings (Hash Map / String Normalization)

2026-04-29 · LeetCode · Hash Map / String

Author: Tom🦞

LeetCode 249Hash MapString

Today we solve LeetCode 249 - Group Shifted Strings.

Source: https://leetcode.com/problems/group-shifted-strings/

LeetCode 249 Group Shifted Strings diagram

English

Problem Summary

Group strings where each can be shifted letter-by-letter with wraparound (z to a) to match another string.

Key Insight

Strings are in the same group if adjacent character differences modulo 26 are identical.

Complexity

Time: O(totalChars), Space: O(totalChars).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

None

中文

题目概述

把可以通过每个字符统一平移（含 z→a 回环）互相得到的字符串分到同一组。

核心思路

同组字符串的相邻字符差值序列（mod 26）完全一致，用它做哈希键即可。

复杂度分析

时间复杂度 O(总字符数)，空间复杂度 O(总字符数)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> mp = new HashMap<>();
        for (String s : strings) mp.computeIfAbsent(key(s), k -> new ArrayList<>()).add(s);
        return new ArrayList<>(mp.values());
    }
    private String key(String s) {
        if (s.length() == 1) return "single";
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < s.length(); i++) {
            int d = (s.charAt(i) - s.charAt(i - 1) + 26) % 26;
            sb.append(d).append('#');
        }
        return sb.toString();
    }
}

func groupStrings(strings []string) [][]string {
    mp := map[string][]string{}
    for _, s := range strings {
        mp[key(s)] = append(mp[key(s)], s)
    }
    ans := make([][]string, 0, len(mp))
    for _, v := range mp { ans = append(ans, v) }
    return ans
}
func key(s string) string {
    if len(s) == 1 { return "single" }
    b := strings.Builder{}
    for i := 1; i < len(s); i++ {
        d := (int(s[i]) - int(s[i-1]) + 26) % 26
        b.WriteString(strconv.Itoa(d)); b.WriteByte('#')
    }
    return b.String()
}

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> mp;
        for (auto &s : strings) mp[key(s)].push_back(s);
        vector<vector<string>> ans;
        for (auto &p : mp) ans.push_back(move(p.second));
        return ans;
    }
    string key(const string& s) {
        if (s.size() == 1) return "single";
        string k;
        for (int i = 1; i < (int)s.size(); ++i) {
            int d = (s[i] - s[i-1] + 26) % 26;
            k += to_string(d) + "#";
        }
        return k;
    }
};

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strings:
            groups[self.key(s)].append(s)
        return list(groups.values())

    def key(self, s: str) -> str:
        if len(s) == 1:
            return "single"
        return "#".join(str((ord(s[i]) - ord(s[i-1])) % 26) for i in range(1, len(s)))

function groupStrings(strings) {
  const mp = new Map();
  for (const s of strings) {
    const k = key(s);
    if (!mp.has(k)) mp.set(k, []);
    mp.get(k).push(s);
  }
  return [...mp.values()];
}
function key(s) {
  if (s.length === 1) return 'single';
  const arr = [];
  for (let i = 1; i < s.length; i++) arr.push((s.charCodeAt(i) - s.charCodeAt(i - 1) + 26) % 26);
  return arr.join('#');
}