Nhóm các chuỗi dịch chuyển (Group Shifted Strings) trong C++

Cho một danh sách các chuỗi không rỗng chỉ chứa chữ cái thường. Ta có thể "dịch chuyển" mỗi ký tự của chuỗi sang ký tự kế tiếp (ví dụ: "abc" → "bcd" → ... → "xyz"). Nhiệm vụ là nhóm tất cả các chuỗi thuộc cùng một chuỗi dịch chuyển.

Ví dụ minh họa

Đầu vào: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
Đầu ra: [["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"]]

Ý tưởng cốt lõi

Hai chuỗi thuộc cùng một nhóm dịch chuyển nếu và chỉ nếu khoảng cách giữa các ký tự liên tiếp của chúng là giống nhau (modulo 26). Ta tính "khóa" (key) cho mỗi chuỗi dựa trên các hiệu số này.

Thuật toán

1. Duyệt qua từng chuỗi trong danh sách.
2. Với mỗi chuỗi, tính chuỗi khóa: key = "#diff1#diff2#..." trong đó diff = (s[i] - s[i-1] + 26) % 26.
3. Sử dụng unordered_map<string, vector<string>> để nhóm các chuỗi theo khóa.
4. Thu thập tất cả các giá trị từ map vào kết quả.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

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

Độ phức tạp

• Thời gian: O(N * L) với N là số chuỗi, L là độ dài trung bình.
• Không gian: O(N * L) để lưu trữ các nhóm.

Kết quả kiểm thử

Đầu vào: {"abc","bcd","acef","xyz","az","ba","a","z"}
Đầu ra: [[az, ba],[a, z],[abc, bcd, xyz],[acef]]