93. Restore IP Addresses

Problem

Bài toán yêu cầu tách một chuỗi số thành các địa chỉ IP hợp lệ (4 phần, mỗi phần từ 0 đến 255, không có số 0 ở đầu trừ khi là "0"). Để giải, ta dùng backtracking (quay lui), thử mọi cách chia chuỗi thành 4 phần, kiểm tra tính hợp lệ từng phần, và thu thập kết quả

Appproach

Duyệt từng vị trí có thể cắt (mỗi phần lấy 1 → 3 ký tự)

Nếu phần đang xét hợp lệ (không bắt đầu bằng '0' trừ khi là '0', giá trị từ 0 đến 255), tiếp tục đệ quy với phần còn lại.

Khi đã có 4 phần và hết chuỗi, ghép lại thành địa chỉ IP và thêm vào kết quả.

Nếu đã đủ 4 phần mà chưa hết chuỗi, hoặc ngược lại, thì loại bỏ (backtrack).

Time and space complexity

TC: Nếu tổng quát với n lớn, độ phức tạp là O(3^4 * n) = O(n), nhưng thực tế với n ≤ 12 thì coi là O(1)

SC:

O(k) với k là số lượng kết quả hợp lệ (không vượt quá vài chục với n ≤ 12).

Tổng thể, O(1) về không gian bổ sung, O(k) cho kết quả trả về.

Solution

typescripttypescript

1function restoreIpAddresses(s: string): string[] {
2    const res: string[] = [];
3    const n = s.length;
4    function backtrack(start: number, path: string[]) {
5        if (path.length === 4 && start === n) {
6            res.push(path.join('.'))
7            return;
8        }
9
10        if (path.length === 4) return;
11
12        for (let len = 1; len <= 3; len++) {
13            if (start + len > n) break;
14            const part = s.substring(start, start + len);
15            if ((part.length > 1 && part[0] === '0') || +part > 255) continue;
16            path.push(part);
17            backtrack(start + len, path);
18            path.pop()
19        }
20    }
21
22    backtrack(0, [])
23    return res
24};

💡

Giải thích

Hàm backtrack(start, path) duyệt từ vị trí start của chuỗi, với các phần đã tách trong path

Nếu đã đủ 4 phần và hết chuỗi, ghép lại thành IP

Mỗi lần thử tách 1, 2 hoặc 3 ký tự, kiểm tra hợp lệ rồi đệ quy tiếp

Nếu phần bắt đầu bằng ‘0’ mà dài hơn 1 ký tự, hoặc giá trị lớn hơn 255 thì bỏ qua

Loading content...

1function restoreIpAddresses(s: string): string[] { 2 const res: string[] = []; 3 const n = s.length; 4 function backtrack(start: number, path: string[]) { 5 if (path.length === 4 && start === n) { 6 res.push(path.join('.')) 7 return; 8 } 9 10 if (path.length === 4) return; 11 12 for (let len = 1; len <= 3; len++) { 13 if (start + len > n) break; 14 const part = s.substring(start, start + len); 15 if ((part.length > 1 && part[0] === '0') || +part > 255) continue; 16 path.push(part); 17 backtrack(start + len, path); 18 path.pop() 19 } 20 } 21 22 backtrack(0, []) 23 return res 24};