93_Restore IP Address

[Medium]

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"

Output:["255.255.11.135", "255.255.111.35"]

Solution 1: iterative

Idea:

• Loop over all possible placements of three periods, and check if all four corresponding substring are between 0 and 255.

• If a substring has length larger than 1 and starts with 0, this substring is invalid.

Time Complexity: $O(n^3)$ where n is the length of input string.

Space Complexity: No extra space needed except the output.

def restoreIpAddresses(s):
    """
    :type s: str
    :rtype: List[str]
    """
    def is_valid_part(s):
        return int(s) >= 256 or (len(s) >= 2 and s[0] == "0")

    if len(s) > 12: return []
    output = []
    for i in range(len(s)-3):
        if not is_valid_part(s[:i+1]):
            for j in range(i+1, len(s)-2):
                if not is_valid_part(s[i+1:j+1]):
                    for k in range(j+1, len(s)-1):
                        if not is_valid_part(s[j+1:k+1]) and not is_valid_part(s[k+1:]):
                            output.append(s[:i+1]+"."+s[i+1:j+1]+"."+s[j+1:k+1]+"."+s[k+1:])
    return output

Solution 2: backtracking