Khôi phục địa chỉ IP trong C++

Giới thiệu

Cho chuỗi chỉ chứa chữ số. Trả về tất cả địa chỉ IP hợp lệ có thể tạo bằng cách chèn 3 dấu chấm. IP hợp lệ: 4 số nguyên 0-255, không số 0 dẫn đầu (trừ "0").

Thuật toán: Backtracking (Quay lui)

Thử tất cả cách đặt 3 dấu chấm (chia chuỗi thành 4 đoạn). Với mỗi đoạn, kiểm tra giá trị 0-255 và không có leading zero.

Cài đặt C++

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

class Solution {
    vector<string> res;
    void backtrack(string& s, int start, int dots, string path) {
        if (dots == 3) {
            string last = s.substr(start);
            if (isValid(last)) res.push_back(path + last);
            return;
        }
        for (int len = 1; len <= 3 && start + len <= s.size(); len++) {
            string seg = s.substr(start, len);
            if (isValid(seg)) {
                backtrack(s, start + len, dots + 1, path + seg + ".");
            }
        }
    }
    bool isValid(string& seg) {
        if (seg.size() > 1 && seg[0] == '0') return false;
        int val = stoi(seg);
        return val >= 0 && val <= 255;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4 || s.size() > 12) return {};
        backtrack(s, 0, 0, "");
        return res;
    }
};

int main() {
    Solution ob;
    auto ans = ob.restoreIpAddresses("25525511135");
    for (auto& ip : ans) cout << ip << '\n';
    // Output: 255.255.11.135, 255.255.111.35
    return 0;
}

Phân tích

• Thời gian: O(1) – tối đa 3^4 = 81 trường hợp (chuỗi dài nhất 12).
• Không gian: O(1) – kết quả tối đa vài chục IP.

LeetCode 93 "Restore IP Addresses".