সমস্যা বিবরণ
শুধু ডিজিট ধারণকারী একটি স্ট্রিং দেওয়া আছে। এটিকে ৪টি পartiশনে ভাগ করে সব সম্ভাব্য বৈধ IP অ্যাড্রেস বের করতে হবে। প্রতিটি পার্ট ০ থেকে ২৫৫ এর মধ্যে হবে এবং ডট দিয়ে আলাদা থাকবে।
উদাহরণ: ip = "25525511136" → আউটপুট ["255.255.11.136", "255.255.111.36"]।
সমাধানের পদ্ধতি
ব্যাকট্র্যাকিং (DFS):
- ৩টি ডট বসাতে হবে (৪টি পার্ট বানাতে)।
- প্রতিটি পার্টের জন্য ১ থেকে ৩ ডিজিট নেওয়া যায়।
- পার্টের মান ০-২৫৫ হলে ভ্যালিড, ২৫৫ এর বেশি হলে ব্রেক।
- রিকার্শন দিয়ে সব কম্বিনেশন ট্রাই করুন।
- বেস কেস: ৩টি ডট বসালে বাকি স্ট্রিং ভ্যালিড কিনা চেক করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long convertToNum(string s, int start, int end) {
long long 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++) {
res += to_string(positions[i]);
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() - startIndex) >= 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;
}
};
int main() {
Solution ob;
string ip = "25525511136";
for (auto& s : ob.genIp(ip)) cout << s << ", ";
return 0;
}
ইনপুট ও আউটপুট
ইনপুট: 25525511136
আউটপুট: [255.255.11.136, 255.255.111.36]
