मान लीजिए हमारे पास केवल अंकों वाली एक स्ट्रिंग है, हमें इसे सभी संभावित वैध IP पते संयोजनों को लौटाकर पुनर्स्थापित करना है। हम जानते हैं कि एक वैध IP पता में ठीक चार पूर्णांक होते हैं (प्रत्येक पूर्णांक 0 से 255 की सीमा में) जो एकल बिंदुओं द्वारा अलग किए जाते हैं।
उदाहरण के लिए, यदि इनपुट "25525511135" है, तो आउटपुट ["255.255.11.135", "255.255.111.35"] होगा।
हल करने की विधि
हम बैकट्रैकिंग का उपयोग करेंगे:
convertToNum()फ़ंक्शन स्ट्रिंग के उपस्ट्रिंग को संख्या में बदलता है, यदि 255 से अधिक तो 10000 लौटाता है।addDots()फ़ंक्शन स्थितियों से IP स्ट्रिंग बनाता है।solve()फ़ंक्शन रिकर्सिवली सभी संभावित विभाजनों को आजमाता है।genIp()मुख्य फ़ंक्शन है जो परिणाम सरणी लौटाता है।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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; } 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 = ""; int x = 0; int posIndex = 0; 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> restoreIpAddresses(string A) { return genIp(A); }}; main(){ Solution ob; print_vector(ob.restoreIpAddresses("25525511135")); }
इनपुट
"25525511135"
आउटपुट
[255.255.11.135, 255.255.111.35, ]
