Restore IP Address

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits from s. You can return the valid IP addresses in any order.

Problem Statement

A valid IP address has exactly four integers, separated by single dots. Each integer must be between 0 and 255 (inclusive), and cannot have leading zeros.

For example:

• "0.1.2.201" and "192.168.1.1" are valid IP addresses.
• "0.011.255.245", "192.168.1.312", and "192.168@1.1" are invalid.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits from s. You can return the valid IP addresses in any order.

Examples

Example 1

Input: s = "25525511135"

Output: ["255.255.11.135", "255.255.111.35"]

Example 2

Input: s = "0000"

Output: ["0.0.0.0"]

Example 3

Input: s = "101023"

Output: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]

Constraints

• 1 ≤ s.length ≤ 20
• s consists of digits only.

Solution

We solve this using backtracking. We try splitting s into four valid parts, one part at a time.

Steps

• We use a helper function, permute(arr, str):
  • arr holds the parts we've already validated and confirmed (up to 3 of them).
  • str holds the remaining string we still need to split up.
• Once arr has 3 parts already, that means only one part is left to form the full IP address. We check if the entire remaining str is valid on its own:
  • If it is, we add it as the final part, and save this complete IP address.
  • If it isn't, this path doesn't lead to a valid IP address, so we simply don't add anything here.
• Otherwise (if we still need more than one part), we try taking the next 1, 2, or 3 characters from str as a possible next part:
  • We check if this piece is a valid number for an IP address segment.
  • If it is, we add it to arr, and recursively call permute again with the rest of the string.
  • If it isn't valid, we skip that length and try the next one.
• We use a helper function, isValid(str), to check if a piece of string can be used as a valid IP segment:
  • It must not be empty.
  • Its numeric value must not be greater than 255.
  • It must not have a leading zero if it's more than one character long (for example, "01" is not allowed, but "0" on its own is fine).
• Once all valid combinations have been explored, we take our results (each stored as an array of 4 parts) and join them with dots to form proper IP address strings.

Code

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

    function permute(arr, str) {

        if (arr.length === 3) {
            if (isValid(str)) {
                result.push([...arr, str]);
                return;
            }
        }

        for (let i = 1; i < 4; i++) {
            let subStr = str.slice(0, i);

            if (!isValid(subStr)) continue;

            permute([...arr, subStr], str.slice(i));
        }
    }

    function isValid(str) {
        if (+str > 255 || !str.length) return false;

        if (str.length >= 2 && str[0] === '0') return false;

        return true;
    }

    permute([], s);

    return result.map(x => x.join('.'));

};