จัดกลุ่มสตริงที่เลื่อนตำแหน่งได้ใน C++

สมมติว่าเรามีสตริง เราสามารถ "เลื่อน" ตัวอักษรแต่ละตัวไปยังตัวอักษรถัดไปได้ เช่น "abc" สามารถเปลี่ยนเป็น "bcd" ได้ เราสามารถทำซ้ำการดำเนินการนี้ซึ่งจะสร้างลำดับ: "abc" → "bcd" → ... → "xyz" หากเรามีรายการสตริงที่ไม่ว่างเปล่าและประกอบด้วยตัวอักษรพิมพ์เล็กเท่านั้น เราต้องจัดกลุ่มสตริงทั้งหมดที่อยู่ในลำดับการเลื่อนเดียวกัน

ตัวอย่าง: อินพุต ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"] ผลลัพธ์: [ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]

วิธีแก้ปัญหา

1. สร้าง map m สำหรับเก็บกลุ่ม
2. สร้างอาร์เรย์ 2 มิติ ret สำหรับผลลัพธ์
3. วนลูปผ่านแต่ละสตริง:
   • สร้าง key จากความต่างระหว่างตัวอักษรที่ติดกัน
   • ถ้าความต่างเป็นลบ ให้บวก 26
   • นำสตริงไปใส่ใน m[key]
4. นำค่าจาก map มาใส่ใน ret
5. คืนค่า ret

ตัวอย่างโค้ด C++

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

void print_vector(vector<vector<string>> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << "["; 
        for(int j = 0; j <v[i].size(); j++){ 
            cout << v[i][j] << ", "; 
        } 
        cout << "],"; 
    } 
    cout << "]"<<endl; 
} 

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

int main(){ 
    Solution ob; 
    vector<string> v = {"abc","bcd","acef","xyz","az","ba","a","z"}; 
    print_vector(ob.groupStrings(v)); 
}

ข้อมูลนำเข้า

{"abc","bcd","acef","xyz","az","ba","a","z"}

ผลลัพธ์

[[az, ba, ],[a, z, ],[abc, bcd, xyz, ],[acef, ],]