🖥 Задача Восстановить IP

Сложность: Средняя

Условие задачи: Рабочий IP-адрес состоит ровно из четырех целых чисел, разделенных одиночными точками. Каждое целое число находится в диапазоне от 0 до 255 (включительно) и не может содержать начальных нулей.

Например, "0.1.2.201" и "192.168.1.1" являются допустимыми IP-адресами, но "0.011.255.245", "192.168.1.312" и "192.168@1.1 " являются недопустимыми IP-адресами.

Учитывая строку s, содержащую только цифры, верните все возможные действительные IP-адреса, которые могут быть сформированы путем вставки точек в s. Вам не разрешается изменять порядок или удалять какие-либо цифры в s. Вы можете вернуть действительные IP-адреса в любом порядке.

Пример:

Ввод: s = "25525511135"

Вывод: ["255.255.11.135","255.255.111.35"]

Ввод: s = "0000"

Вывод: ["0.0.0.0"]

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # dfs and backtracking
        self.s = s
        self.len_s = len(s)
        self.ans = []

        self.dfs(0, [])

        return self.ans

    def dfs(self, index, partition):
        if index == self.len_s:
            # we reached the end of the string
            if len(partition) == 4:
                self.ans.append(".".join(partition))
            return
        
        if index < self.len_s and len(partition) == 4:
            # we haven't used all the characters to build 4 address fields
            return

        if self.s[index] == '0':
            partition.append('0')
            self.dfs(index + 1, partition)
            partition.pop()
        else:
            for i in range(index + 1, self.len_s + 1):
                if 0 <= int(self.s[index: i]) <= 255:
                    partition.append(self.s[index: i])
                    self.dfs(i, partition)
                    partition.pop()
                else:
                    # no need to check further as the value is not in the range of 0 ~ 255
                    break