Chương trình khôi phục địa chỉ IP từ xâu số trong C++

Mô tả bài toán

Cho xâu chỉ chứa chữ số, chèn 3 dấu chấm để tạo thành địa chỉ IP hợp lệ (4 phần, mỗi phần 0-255, không có leading zeros trừ số 0). Trả về tất cả các địa chỉ IP có thể.

Ví dụ: "25525511136" → ["255.255.11.136", "255.255.111.36"].

Giải thuật (Backtracking)

1. Hàm convertToNum(s, start, end) chuyển thành số, trả về >255 nếu vượt quá.
2. Hàm addDots(positions) ghép thành xâu IP.
3. Hàm solve(s, result, positions, dotCount, startIndex):
   • Nếu dotCount==0 và phần còn lại hợp lệ: thêm vào kết quả.
   • Với i từ startIndex đến n-1: nếu đoạn startIndex..i hợp lệ, thêm vào positions, đệ quy dotCount-1, i+1, rồi backtrack.

Ví dụ minh họa (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 dotCount=3, int start=0) {
        if (dotCount == 0 && (int)s.size()-start >= 1) {
            long long num = convertToNum(s, start, s.size()-1);
            if (num >= 0 && num <= 255) {
                pos.push_back(num);
                string ip = addDots(pos);
                if (ip.size() - 3 == s.size()) res.push_back(ip);
                pos.pop_back();
            }
            return;
        }
        for (int i = start; i < s.size(); i++) {
            long long num = convertToNum(s, start, i);
            if (num >= 0 && num <= 255) {
                pos.push_back(num);
                solve(s, res, pos, dotCount-1, i+1);
                pos.pop_back();
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<int> pos;
        solve(s, res, pos);
        return res;
    }
};

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

Đầu vào

25525511136

Đầu ra

255.255.11.136
255.255.111.36