স্ট্রিং থেকে বৈধ IP ঠিকানা পুনঃস্থাপন করা C++-এ

সমস্যা বিবরণ

শুধু ডিজিট ধারণকারী একটি স্ট্রিং দেওয়া আছে। এর মধ্যে তিনটি ডট (.) যোগ করে সকল সম্ভাব্য বৈধ IPv4 ঠিকানা বের করতে হবে। প্রতিটি অংশ ০ থেকে ২৫৫ এর মধ্যে হবে এবং লিডিং জিরো থাকতে পারবে না (সوى "০" বাদে)।

উদাহরণ

ইনপুট: "25525511135"

আউটপুট: ["255.255.11.135", "255.255.111.35"]

অ্যালগরিদম: ব্যাকট্র্যাকিং (DFS)

1. প্রতিটি ডটের পজিশন ট্রাই করুন (রিকার্সিভলি)।
2. প্রতিটি সেগমেন্টের জন্য:
   • দৈর্ঘ্য ১ থেকে ৩ হতে পারে।
   • স্ট্রিং থেকে সংখ্যা বের করুন।
   • যদি ০-২৫৫ এর মধ্যে হয় এবং লিডিং জিরো না থাকে, তবে রিকার্সিভ কল করুন।
3. ৩টি ডট প্লেস হলে (অর্থাৎ ৪টি সেগমেন্ট হলে), শেষ সেগমেন্ট চেক করুন।
4. বৈধ হলে ফলাফলে যোগ করুন।

C++ বাস্তবায়ন

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

class Solution {
public:
    int 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; // invalid
        }
        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, int startIndex) {
        if (dotCount == 0) {
            int len = s.size() - startIndex;
            if (len >= 1 && len <= 3) {
                int num = convertToNum(s, startIndex, s.size() - 1);
                if (num >= 0 && num <= 255) {
                    // লিডিং জিরো চেক
                    if (len > 1 && s[startIndex] == '0') return;
                    positions.push_back(num);
                    string ip = addDots(positions);
                    if (ip.size() - 3 == s.size()) result.push_back(ip);
                    positions.pop_back();
                }
            }
            return;
        }

        for (int i = startIndex; i < startIndex + 3 && i < s.size(); i++) {
            int len = i - startIndex + 1;
            if (len > 1 && s[startIndex] == '0') break; // লিডিং জিরো
            int num = convertToNum(s, startIndex, i);
            if (num >= 0 && num <= 255) {
                positions.push_back(num);
                solve(s, result, positions, dotCount - 1, i + 1);
                positions.pop_back();
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        vector<int> positions;
        solve(s, result, positions, 3, 0);
        return result;
    }
};

int main() {
    Solution ob;
    auto res = ob.restoreIpAddresses("25525511135");
    for (auto& ip : res) cout << ip << endl;
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(1) — ইনপুট সাইজ ফিক্সড (সর্বোচ্চ ১২ ডিজিট), কনস্ট্যান্ট সংখ্যক কোম্বিনেশন।
• স্থান জটিলতা: O(1) — আউটপুট বাদে।