Действительный 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-адреса в любом порядке.


class Solution(object):
    def restoreIpAddresses(self, s):
        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 (int(s[i: j + 1]) < 256) and (i == j or s[i] != "0"):
                    backtrack(j + 1, dots + 1, curIP + s[i: j+1] + ".")


        backtrack(0, 0, "")
        return res



Войти в полноэкранный режим

Выйти из полноэкранного режима