Làm thế nào để xây dựng thuật toán Backtracking giải quyết bài toán Restore IP Addresses và xử lý các trường hợp ngoại lệ về định dạng số?

Question

Accepted Answer

Bản chất vấn đề Cho một chuỗi chỉ gồm các chữ số, hãy trả về tất cả các địa chỉ IP hợp lệ có thể được tạo ra bằng cách chèn dấu chấm vào chuỗi đó. Một địa chỉ IP hợp lệ gồm 4 phần, mỗi phần từ 0 đến 255 và không có số 0 đứng đầu (trừ khi chính là số 0). Cơ chế hoạt động của Backtracking Hàm đệ quy cần theo dõi 2 tham số chính: vị trí hiện tại trong chuỗi (startIndex) và số lượng phần đã tách được (segmentCount). Điều kiện dừng: Khi đã tách đủ 4 phần và duyệt hết toàn bộ chuỗi ký tự, thêm địa chỉ IP vào kết quả. Nếu đã đủ 4 phần nhưng chưa hết chuỗi, hoặc hết chuỗi mà chưa đủ 4 phần thì cắt nhánh (Pruning). Trong mỗi bước, thử cắt từ 1 đến 3 ký tự làm một phần IP, kiểm tra tính hợp lệ. Ví dụ cài đặt mã nguồn (Java) class Solution { public List restoreIpAddresses(String s) { List result = new ArrayList<>(); backtrack(s, 0, 0, "", result); return result; } private void backtrack(String s, int startIndex, int segmentCount, String currentIp, List result) { if (segmentCount == 4 && startIndex == s.length()) { result.add(currentIp.substring(1)); // Bỏ dấu chấm thừa ở đầu return; } if (segmentCount == 4 || startIndex == s.length()) { return; } for (int i = 1; i <= 3; i++) { if (startIndex + i > s.length()) break; String segment = s.substring(startIndex, startIndex + i); if (isValid(segment)) { backtrack(s, startIndex + i, segmentCount + 1, currentIp + "." + segment, result); } } } private boolean isValid(String segment) { if (segment.length() > 1 && segment.startsWith("0")) return false; int val = Integer.parseInt(segment); return val >= 0 && val <= 255; } } Tối ưu hóa và Kinh nghiệm thực chiến Pruning theo độ dài: Một IP hợp lệ có độ dài tối thiểu là 4 và tối đa là 12 ký tự. Có thể kiểm tra nhanh độ dài của chuỗi đầu vào ở bước khởi tạo để trả về mảng rỗng. Xử lý số 0 đứng đầu: Lỗi phổ biến của lập trình viên cấp độ Junior là cho phép các đoạn như 01, 00 vượt qua bước kiểm tra hợp lệ.

Làm thế nào để xây dựng thuật toán Backtracking giải quyết bài toán Restore IP Addresses và xử lý các trường hợp ngoại lệ về định dạng số?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi backtracking liên quan cùng chủ đề