โปรแกรมหาทุก IP Address ที่เป็นไปได้จากสตริงตัวเลขใน C++

ให้สตริงตัวเลข ต้องการสร้าง IP Address ทุกแบบที่ถูกต้อง (4 ส่วน, แต่ละส่วน 0-255, ไม่มี leading zeros ยกเว้น 0 เอง)

ตัวอย่าง: "25525511136" → ["255.255.11.136", "255.255.111.36"]

ขั้นตอนการแก้ปัญหา (Backtracking)

1. ฟังก์ชัน convertToNum(s, start, end): แปลง substring เป็นตัวเลข ถ้า >255 คืน 10000
2. ฟังก์ชัน addDots(positions): รวมตัวเลขด้วย '.' คืนสตริง IP
3. ฟังก์ชัน solve(s, result, positions, dotsLeft=3, startIdx=0):
   • ถ้า dotsLeft==0: ตรวจสอบส่วนท้าย ถ้าถูกต้อง → เพิ่ม IP เข้า result
   • วน i = startIdx ถึง s.size()-1:
     • num = convertToNum(s, startIdx, i)
     • ถ้า 0 <= num <= 255: เพิ่มเข้า positions, เรียก solve(dotsLeft-1, i+1), pop_back

ตัวอย่างโค้ด C++

#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>& pos) {
        string res;
        for (int i = 0; i < pos.size(); i++) {
            res += to_string(pos[i]);
            if (i < pos.size()-1) res += '.';
        }
        return res;
    }
    void solve(string s, vector<string>& res, vector<int>& pos, int dots=3, int start=0) {
        if (dots == 0 && (int)s.size()-start >= 1) {
            int num = convertToNum(s, start, s.size()-1);
            if (0 <= num && num <= 255) {
                pos.push_back(num);
                string ip = addDots(pos);
                if ((int)ip.size() - 3 == s.size()) res.push_back(ip);
                pos.pop_back();
            }
            return;
        }
        for (int i = start; i < s.size(); i++) {
            int num = convertToNum(s, start, i);
            if (0 <= num && num <= 255) {
                pos.push_back(num);
                solve(s, res, pos, dots-1, i+1);
                pos.pop_back();
            }
        }
    }
    vector<string> get_ip(string A) {
        vector<string> res; vector<int> pos;
        solve(A, res, pos); return res;
    }
};

int main() {
    Solution ob;
    for (auto& s : ob.get_ip("25525511136")) cout << s << '\n';
    return 0;
}

อินพุต

25525511136

เอาต์พุต

255.255.11.136
255.255.111.36