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};

93. Restore IP Addresses

Related Posts

Related Posts

93. Restore IP Addresses

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists