C++ में जनरलाइज़्ड एब्रीविएशन - शब्द के सभी संक्षिप्त रूप उत्पन्न करें

समस्या विवरण

मान लीजिए कोई शब्द है। हमें एक फ़ंक्शन परिभाषित करना है जो उस शब्द के जनरलाइज़्ड एब्रीविएशन उत्पन्न कर सके।

उदाहरण के लिए, यदि इनपुट "word" है, तो आउटपुट ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"] होगा।

समाधान दृष्टिकोण

बैकट्रैकिंग का उपयोग करके सभी संभावित संक्षिप्त रूप उत्पन्न करें:

1. एक सरणी ret परिभाषित करें
2. solve() फ़ंक्शन परिभाषित करें जो s, idx लेता है:
   • यदि idx >= s का आकार, तो s को ret में डालें और लौटें
   • y := s का सबस्ट्रिंग सूचकांक 0 से idx-1 तक
   • i := y का आकार - 1
   • num := खाली स्ट्रिंग
   • जब (i >= 0 और y[i] अंक है):
     • num := y[i] + num
     • i घटाएं
   • यदि i != y का आकार - 1:
     • नई स्ट्रिंग बनाएं जहां संख्या बढ़ाई गई हो
     • पुनरावर्ती कॉल करें
   • अन्यथा:
     • prev := s[idx], s[idx] := '1', पुनरावर्ती कॉल, s[idx] := prev
   • solve(s, idx + 1) कॉल करें
3. मुख्य विधि से: solve(word, 0) कॉल करें और ret लौटाएं

C++ कार्यान्वयन

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

void print_vector(vector<auto> 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 = 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, idx); 
            else 
                solve(ret, 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, ]