C++ में स्ट्रिंग्स को एनकोड और डिकोड करें - लंबाई-उपसर्ग एन्कोडिंग

समस्या विवरण

मान लीजिए हमारे पास स्ट्रिंग्स की एक सूची है। हमें एक एल्गोरिदम डिजाइन करना है जो स्ट्रिंग्स की सूची को एक स्ट्रिंग में एनकोड कर सके। हमें एक डिकोडर भी बनाना है जो वापस स्ट्रिंग्स की मूल सूची में डिकोड कर सके। मान लीजिए एनकोडर और डिकोडर इन मशीनों पर इंस्टॉल हैं, और दो अलग-अलग फ़ंक्शन हैं:

मशीन 1 (भेजने वाला) का फ़ंक्शन

string encode(vector<string> strs) { 
    // स्ट्रिंग्स पढ़ने और एन्कोडेड_स्ट्रिंग लौटाने का कोड 
}

मशीन 2 (प्राप्तकर्ता) का फ़ंक्शन

vector<string> decode(string s) { 
    // एन्कोडेड_स्ट्रिंग को डिकोड करके strs लौटाने का कोड 
}

उदाहरण के लिए, यदि इनपुट {"hello", "world", "coding", "challenge"} है, तो आउटपुट होगा: एन्कोडेड स्ट्रिंग 5#hello5#world6#coding9#challenge, डिकोडेड रूप [hello, world, coding, challenge, ]

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

लंबाई-उपसर्ग एन्कोडिंग (Length-Prefix Encoding):

1. encode() फ़ंक्शन:
   • ret := खाली स्ट्रिंग
   • प्रत्येक स्ट्रिंग के लिए: ret += स्ट्रिंग की लंबाई + "#" + स्ट्रिंग
   • ret लौटाएं
2. getNext() फ़ंक्शन: दिए गए वर्ण की अगली स्थिति ढूंढें
3. decode() फ़ंक्शन:
   • ret सरणी परिभाषित करें
   • i := 0, n := s का आकार
   • जब i < n:
     • hashPos := getNext('#', i, s)
     • len := s के सबस्ट्रिंग (i से hashPos-i-1) को पूर्णांक में पार्स करें
     • i := hashPos + 1
     • s के सबस्ट्रिंग (i से len-1) को ret में जोड़ें
     • i := i + len
   • 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 Codec { 
public: 
    string encode(vector<string>& strs) { 
        string ret = ""; 
        for (int i = 0; i < strs.size(); i++) { 
            ret += to_string(strs[i].size()) + "#" + strs[i]; 
        } 
        return ret; 
    } 
    
    int getNext(char x, int start, string s){ 
        int idx = s.size(); 
        for (int i = start; i < s.size(); i++) { 
            if (s[i] == x) { 
                idx = i; 
                break; 
            } 
        } 
        return idx; 
    } 
    
    vector<string> decode(string s) { 
        vector<string> ret; 
        int i = 0; 
        int n = s.size(); 
        while (i < n) { 
            int hashPos = getNext('#', i, s); 
            int len = stoi(s.substr(i, hashPos - i)); 
            i = hashPos + 1; 
            ret.push_back(s.substr(i, len)); 
            i += len; 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Codec ob; 
    vector<string> v = {"hello", "world", "coding", "challenge"}; 
    string enc = (ob.encode(v)); 
    cout << "Encoded String " << enc << endl; 
    print_vector(ob.decode(enc)); 
    return 0;
}

इनपुट

{"hello", "world", "coding", "challenge"}

आउटपुट

Encoded String 5#hello5#world6#coding9#challenge [hello, world, coding, challenge, ]