תיאור השאלה
A valid IP address consists of exactly four integers between 0 and 255, separated by single dots, with no leading zeros. Given a string s containing only digits, return all valid IP addresses that can be formed by inserting dots into s. You may not reorder or remove any digits.
איך פותרים?
Backtracking: בכל שלב חותכים את החלק הבא באורך 1 עד 3 ספרות, ובודקים שהוא בין 0 ל־255 ושאין בו אפס מוביל. אחרי ארבעה חלקים שומרים את הכתובת אם כל הספרות נוצלו. מספר האפשרויות חסום (3⁴), אז זה מהיר מאוד.
פתרון קוד
JavaScript
Python
function restoreIpAddresses(s) {
const result = [];
const parts = [];
function backtrack(start) {
if (parts.length === 4) {
if (start === s.length) result.push(parts.join("."));
return;
}
for (let len = 1; len <= 3 && start + len <= s.length; len++) {
const part = s.slice(start, start + len);
if ((part.length > 1 && part[0] === "0") || Number(part) > 255) break;
parts.push(part);
backtrack(start + len);
parts.pop();
}
}
backtrack(0);
return result;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.