C++-এ Generalized Abbreviation: শব্দের সাধারণীকৃত সংক্ষিপ্তরূপ জেনারেট করা

একটি শব্দ দেওয়া আছে। এর সকল সম্ভাব্য জেনারেলাইজড অ্যাব্রিভিয়েশন (Generalized Abbreviation) জেনারেট করতে হবে। অ্যাব্রিভিয়েশনে যেকোনো সাবস্ট্রিংকে তার দৈর্ঘ্যের সংখ্যা দিয়ে প্রতিস্থাপন করা যায়।

উদাহরণ

ইনপুট: "word"

আউটপুট: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

সমাধানের পদ্ধতি (Backtracking / Recursion)

1. ফলাফল সংরক্ষণের জন্য ret ভেক্টর।
2. রিকারসিভ ফাংশন solve(s, idx):
   • যদি idx >= s.size(), তবে s কে ret-এ পুশ করে রিটার্ন।
   • কারেন্ট প্রিফিক্স y = s.substr(0, idx) নিন।
   • y-র শেষ থেকে শুরুর দিকে ডিজিট স্ক্যান করুন (num স্ট্রিং হিসেবে)।
   • যদি শেষে ডিজিট পাওয়া যায় (i != y.size()-1):
     • সেই নাম্বারটি ১ বাড়িয়ে নতুন স্ট্রিং বানান।
     • নতুন স্ট্রিং দিয়ে রিকারসিভ কল (ইনডেক্স অ্যাডজাস্ট করে)।
   • অন্যথায় (শেষে ডিজিট নেই):
     • কারেন্ট ক্যারেক্টারকে '1' দিয়ে রিপ্লেস করুন।
     • রিকারসিভ কল।
     • ব্যাকট্র্যাক (পুরনো ক্যারেক্টার ফিরিয়ে দিন)।
   • কারেন্ট ক্যারেক্টার অপরিবর্তিত রেখে রিকারসিভ কল (solve(s, idx+1))।
3. মেইন থেকে solve(word, 0) কল করুন।

C++ কোড উদাহরণ

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

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

class Solution {
public:
    vector<string> ret;
    
    void solve(string s, int idx) {
        if (idx >= s.size()) {
            ret.push_back(s);
            return;
        }
        string y = s.substr(0, idx);
        int i = y.size() - 1;
        string num = "";
        while (i >= 0 && y[i] <= '9' && y[i] >= '0') {
            num = y[i] + num;
            i--;
        }
        if (i != y.size() - 1) {
            string ret_str = s.substr(0, idx - (y.size() - 1 - i)) + to_string(stoi(num) + 1) + s.substr(idx + 1);
            string s1 = to_string(stoi(num) + 1);
            string s2 = to_string(stoi(num));
            if (s1.size() == s2.size())
                solve(ret_str, idx);
            else
                solve(ret_str, idx + 1);
        } else {
            char prev = s[idx];
            s[idx] = '1';
            solve(s, idx + 1);
            s[idx] = prev;
        }
        solve(s, idx + 1);
    }
    
    vector<string> generateAbbreviations(string word) {
        solve(word, 0);
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.generateAbbreviations("hello"));
    return 0;
}

ইনপুট

hello

আউটপুট

[5, 4o, 3l1, 3lo, 2l2, 2l1o, 2ll1, 2llo, 1e3, 1e2o, 1e1l1, 1e1lo, 1el2, 1el1o, 1ell1, 1ello, h4, h3o, h2l1, h2lo, h1l2, h1l1o, h1ll1, h1llo, he3, he2o, he1l1, he1lo, hel2, hel1o, hell1, hello, ]