LietCode
Restore IP Addresses

Restore IP Addresses

Abhi's photo
Abhi
·

4 min read

Explain the Problem

Given a string containing only digits, return all possible valid IP addresses that can be obtained by inserting dots into the string. You can return the answer in any order.

A valid IP address consists of exactly four integers (each between 0 and 255) separated by single dots and cannot have leading zeros (except for the number 0 itself).

Example:

Input: s = "25525511135"

Output:

[
  "255.255.11.135",
  "255.255.111.35"
]

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

  1. Recursive Function: We'll create a helper function that tries to insert dots into the string to form valid IP addresses.

  2. Valid Segment Check: Ensure each segment of the IP address is a valid number between 0 and 255 and does not have leading zeros.

  3. Backtracking: If a valid IP address is formed (with exactly four segments), we add it to the result list.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

function restoreIpAddresses(s) {
  const result = [];

  // Helper function to check if a segment is valid
  function isValid(segment) {
    if (segment.length > 1 && segment[0] === '0') return false; // no leading zeros
    return parseInt(segment, 10) >= 0 && parseInt(segment, 10) <= 255;
  }

  // Helper function for backtracking
  function backtrack(start, path) {
    // If we have 4 segments and have used all characters, add to result
    if (path.length === 4 && start === s.length) {
      result.push(path.join('.'));
      return;
    }

    // If we have 4 segments but still have characters left, return
    if (path.length === 4) return;

    // Try to create segments of length 1 to 3
    for (let length = 1; length <= 3; length++) {
      if (start + length > s.length) break; // exceed string length
      const segment = s.substring(start, start + length);
      if (isValid(segment)) {
        path.push(segment);
        backtrack(start + length, path);
        path.pop();
      }
    }
  }

  // Start the backtracking with an empty path
  backtrack(0, []);

  return result;
}

Explanation of the Solution in Simple Terms

Imagine you have a string of digits, and you want to insert dots to form a valid IP address. A valid IP address has four parts, each part is between 0 and 255, and it can't have leading zeros (except for the number 0 itself).

  • Recursive Function: This is like a helper that tries to place dots in different positions to form valid parts.

  • Valid Segment Check: This means ensuring each part is a number between 0 and 255 and doesn’t start with a zero unless it’s the number 0.

  • Backtracking: This means if the current way of placing dots doesn’t form a valid IP address, you go back and try a different way.

For each position in the string, you try to form segments of length 1 to 3. If the segment is valid, you add it to your current path and continue. If you form a valid IP address (four parts and no leftover characters), you save it. If not, you undo your last step and try another segment.

Code Explanation in Pointers

  1. Initialize Result Array: Create an empty array to store all valid IP addresses.

  2. Define Valid Segment Check: Create a function to check if a segment is valid (between 0 and 255 and no leading zeros).

  3. Define Backtracking Function: Create a recursive function to explore different ways to insert dots.

  4. Base Case - Valid IP Address Formed: If the path has 4 segments and all characters are used, add the current IP address to the result.

  5. Base Case - Too Many Segments: If the path has 4 segments but characters are left, return.

  6. Try Segment Lengths: Try to form segments of length 1 to 3.

  7. Check Validity: If the segment is valid, add it to the path.

  8. Recursive Call: Call the function recursively with the updated path.

  9. Backtrack: Remove the last segment from the path before trying the next one.

  10. Start Search: Start the search with an empty path.

Complexity Analysis

  • Time Complexity: O(3^N), where N is the length of the string. This is because we try to create segments of length 1 to 3 at each position.

  • Space Complexity: O(N), due to the recursion stack and the path array.

backtracking