IP 주소 복원

유효한 IP 주소는 단일 점으로 구분된 정확히 4개의 정수로 구성됩니다. 각 정수는 0에서 255(포함) 사이이며 앞에 0이 올 수 없습니다.

예를 들어 "0.1.2.201"및 "192.168.1.1"은 유효한 IP 주소이지만 "0.011.255.245", "192.168.1.312"및 "[email protected] "은 잘못된 IP 주소입니다.
숫자만 포함된 문자열 s가 주어지면 s에 점을 삽입하여 형성할 수 있는 가능한 모든 유효한 IP 주소를 반환합니다. 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