93. Restore IP Addresses - Explanation

Description

A valid IP address consists of exactly four integers separated by single dots. Each integer is 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, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

You are 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 in s. You may return the valid IP addresses in any order.

Example 1:

Input: s = "101023"

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

Example 2:

Input: s = "010010"

Output: ["0.10.0.10","0.100.1.0"]

Constraints:

1 <= s.length <= 20
s consists of digits only.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Backtracking

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        if len(s) > 12:
            return res

        def backtrack(i, dots, curIP):
            if dots == 4 and i == len(s):
                res.append(curIP[:-1])
                return
            if dots > 4:
                return

            for j in range(i, min(i + 3, len(s))):
                if i != j and s[i] == "0":
                    continue
                if int(s[i: j + 1]) < 256:
                    backtrack(j + 1, dots + 1, curIP + s[i: j + 1] + ".")

        backtrack(0, 0, "")
        return res

Time & Space Complexity

Time complexity: $O(m ^ n * n)$
Space complexity: $O(m * n)$

Where $m$ is equals to $3$ as there are at most three digits in a valid segment and $n$ is equals to $4$ as there are four segments in a valid IP.

2. Iteration

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        if len(s) > 12:
            return res

        def valid(num):
            return len(num) == 1 or (int(num) < 256 and num[0] != "0")

        def add(s1, s2, s3, s4):
            if s1 + s2 + s3 + s4 != len(s):
                return

            num1 = s[:s1]
            num2 = s[s1:s1+s2]
            num3 = s[s1+s2:s1+s2+s3]
            num4 = s[s1+s2+s3:]
            if valid(num1) and valid(num2) and valid(num3) and valid(num4):
                res.append(num1 + "." + num2 + "." + num3 + "." + num4)

        for seg1 in range(1, 4):
            for seg2 in range(1, 4):
                for seg3 in range(1, 4):
                    for seg4 in range(1, 4):
                        add(seg1, seg2, seg3, seg4)

        return res

Time & Space Complexity

Time complexity: $O(m ^ n * n)$
Space complexity: $O(m * n)$

Where $m$ is equals to $3$ as there are at most three digits in a valid segment and $n$ is equals to $4$ as there are four segments in a valid IP.