C++ में रिस्टोरेशन के बाद सभी संभावित IP एड्रेस ढूंढने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास केवल अंकों वाली एक स्ट्रिंग है, हमें इसे सभी संभावित वैध IP एड्रेस कॉम्बिनेशन बनाकर रिस्टोर करना है। हम जानते हैं कि एक वैध IP एड्रेस में ठीक चार पूर्णांक होते हैं (प्रत्येक पूर्णांक 0 से 255 की रेंज में) जो सिंगल पीरियड सिंबल से अलग होते हैं।

उदाहरण के लिए, यदि इनपुट है ip = "25525511136", तो आउटपुट ["254.25.40.123", "254.254.0.123"] होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम बैकट्रैकिंग का उपयोग करेंगे:

1. एक फंक्शन convertToNum() परिभाषित करें जो s, start, end लेता है
2. num := 0
3. i := start से end तक:
   • num := (num * 10) + (s[i] - '0' का ASCII)
   • यदि num > 255, तो 10000 वापस करें
4. num वापस करें
5. एक फंक्शन addDots() परिभाषित करें जो positions लेता है
6. res := खाली स्ट्रिंग
7. positions में प्रत्येक के लिए: num को स्ट्रिंग में बदलें, res में जोड़ें, यदि अंतिम नहीं है तो "." जोड़ें
8. res वापस करें
9. एक फंक्शन solve() परिभाषित करें जो s, result ऐरे, positions ऐरे, dotCount (3 से आरंभ), startIndex (0 से आरंभ) लेता है
   • यदि dotCount 0 नहीं है और शेष स्ट्रिंग की लंबाई >= 1:
     • temp := convertToNum(s, startIndex, s का आकार)
     • यदि 0 <= temp <= 255: temp को positions में जोड़ें, res := addDots(positions), यदि res का आकार == s का आकार + 3, तो result में res जोड़ें
   • वापस करें
10. i := startIndex से s के आकार तक:
    • temp := convertToNum(s, startIndex, i)
    • यदि 0 <= temp <= 255: temp को positions में जोड़ें, solve(s, result, positions, dotCount-1, i+1), positions से अंतिम तत्व हटाएं
11. एक फंक्शन genIp परिभाषित करें जो स्ट्रिंग s लेता है
    • result ऐरे, position ऐरे परिभाषित करें
    • solve(s, result, position) कॉल करें
    • result वापस करें
12. मुख्य विधि से genIp(A) कॉल करें

उदाहरण

#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;
}

typedef long long int lli;

class Solution {
public:
    lli convertToNum(string s, int start, int end) {
        lli num = 0;
        for (int i = start; i <= end; i++) {
            num = (num * 10) + (s[i] - '0');
            if (num > 255) return 10000;
        }
        return num;
    }
    
    string addDots(vector<int> positions) {
        string res = "";
        for (int i = 0; i < positions.size(); i++) {
            int num = positions[i];
            ostringstream str1;
            str1 << num;
            string temp = str1.str();
            res += temp;
            if (i < positions.size() - 1) res += ".";
        }
        return res;
    }
    
    void solve(string s, vector<string>& result, vector<int> positions, int dotCount = 3, int startIndex = 0) {
        if (!dotCount && ((s.size() - 1) - startIndex + 1) >= 1) {
            int temp = convertToNum(s, startIndex, s.size() - 1);
            if (temp >= 0 && temp <= 255) {
                positions.push_back(temp);
                string res = addDots(positions);
                if (res.size() - 3 == s.size()) {
                    result.push_back(res);
                }
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            int temp = convertToNum(s, startIndex, i);
            if (temp >= 0 && temp <= 255) {
                positions.push_back(temp);
                solve(s, result, positions, dotCount - 1, i + 1);
                positions.pop_back();
            }
        }
    }
    
    vector<string> genIp(string s) {
        vector<string> result;
        vector<int> position;
        solve(s, result, position);
        return result;
    }
    
    vector<string> get_ip(string A) {
        return genIp(A);
    }
};

int main() {
    Solution ob;
    string ip = "25525511136";
    print_vector(ob.get_ip(ip));
}

इनपुट

25525511136

आउटपुट

[255.255.11.136, 255.255.111.36, ]