Restore IP Addresses – เรียกคืนที่อยู่ IP ใน C++

ปัญหา: Restore IP Addresses

กำหนดสตริงตัวเลข בלבד ใส่จุด (.) เพื่อแบ่งเป็น 4 ส่วน แต่ละส่วนเป็นจำนวนเต็ม 0-255 ไม่มี leading zeros (ยกเว้น 0 เอง) หา ทุกความเป็นไปได้

ตัวอย่าง

Input: "25525511135"

Output: ["255.255.11.135", "255.255.111.35"]

แนวทางแก้ปัญหา: Backtracking (DFS)

ข้อสังเกต

• IP address มี 4 ส่วน → ต้องวางจุด 3 จุด
• แต่ละส่วนยาว 1-3 หลัก
• ค่าต้อง ≤ 255
• Backtracking: ลองวางจุดทุกตำแหน่งที่เป็นไปได้

ขั้นตอน

1. ฟังก์ชัน solve(s, result, path, dotsLeft, startIdx)
2. Base case: dotsLeft == 0 → ตรวจสอบส่วนสุดท้าย (startIdx ถึงจบ) ว่า valid ไหม → เพิ่มใน result
3. Recursive: ลองตัดส่วนถัดไปยาว 1, 2, 3 ตัว
   • แปลงเป็นตัวเลข → ถ้า ≤ 255 และไม่มี leading zeros → ใส่ path → เรียก solve(dotsLeft-1, nextIdx)
   • Backtrack: pop path

ตัวอย่างโค้ด C++ (Backtracking สะอาด)

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

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        vector<string> path;
        backtrack(s, 0, path, result);
        return result;
    }

    void backtrack(const string& s, int start, vector<string>& path,
                   vector<string>& result) {
        if (path.size() == 4) {
            if (start == s.size()) {
                string ip = path[0] + "." + path[1] + "." + path[2] + "." + path[3];
                result.push_back(ip);
            }
            return;
        }

        for (int len = 1; len <= 3 && start + len <= s.size(); len++) {
            string segment = s.substr(start, len);
            if (isValid(segment)) {
                path.push_back(segment);
                backtrack(s, start + len, path, result);
                path.pop_back();
            }
        }
    }

    bool isValid(const string& seg) {
        if (seg.size() > 1 && seg[0] == '0') return false; // leading zero
        int val = stoi(seg);
        return val >= 0 && val <= 255;
    }
};

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

โค้ดต้นฉบับ (Iterative String Building)

// ใช้ convertToNum, addDots, solve แบบ manual string manipulation
// ซับซ้อนกว่า backtracking มาตรฐาน

ความซับซ้อน

• เวลา: O(1) – สตริงยาวสูงสุด 12 ตัว (4×3), จำนวนความเป็นไปได้คงที่ (~3⁴ = 81)
• พื้นที่: O(1) – recursion depth = 4, output size ≤ constant

ข้อสังเกต

• LeetCode 93 – Backtracking คลาสสิก
• Pruning สำคัญ: ตัดทิ้งเร็วถ้า segment > 255 หรือ leading zero
• ใช้ stoi แปลงสตริงเป็น int ง่ายกว่าการคำนวณ manual
• เวอร์ชัน iterative (3 nested loops) ก็ได้ แต่ backtracking อ่านง่ายกว่า