C++-এ শিফটেড স্ট্রিং গ্রুপিং

ধরা যাক একটি স্ট্রিং আছে, আমরা এর প্রতিটি অক্ষরকে পরবর্তী অক্ষরে শিফট করতে পারি, যেমন: "abc" কে "bcd" এ রূপান্তর করা যায়। এই অপারেশনটি বারবার করে একটি সিকোয়েন্স তৈরি করা যায়: "abc" → "bcd" → ... → "xyz"। যদি আমাদের একটি লিস্ট থাকে যেটিতে শুধু ছোট হাতের ইংরেজি অক্ষর থাকে, তবে একই শিফটিং সিকোয়েন্সের স্ট্রিংগুলো গ্রুপ করতে হবে।

যেমন, ইনপুট হলে ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], তবে আউটপুট হবে [["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"]]

সমাধানের ধাপগুলো:

• একটি ম্যাপ m ডিফাইন করব

• একটি ২ডি অ্যারে ret ডিফাইন করব

• প্রতি স্ট্রিংয়ের জন্য একটি কী তৈরি করব:

  • key := ""

  • প্রতি অক্ষরের পার্থক্য গণনা করব: diff := strings[i][j] - strings[i][j-1]

  • যদি diff < 0 হয়, তবে diff += 26

  • key := key + "#" + to_string(diff)

• স্ট্রিংটি m[key] এ যোগ করব

• ম্যাপের সব ভ্যালু ret এ যোগ করব

• ret রিটার্ন করব

উদাহরণ

নিচের কোডটি দেখুন ভালো বুঝতে −

#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, ],]