[LeetCode] Restore IP Addresses

재귀

Leet Code

medium

문제

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses and “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses.

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Input: s = "0000"
Output: ["0.0.0.0"]

완전탐색으로 3^4의 경우의 수를 검색한다.

***.***.***.*** 의 각 * 칸에 한 자리 수, 두 자리 수, 세 자리 수가 들어갈 수 있으므로 3^4 경우의 수를 가진다.

따라서 재귀로 해당 경우의 수를 모두 탐색한다.

def findIP(array, s):
    if len(array) == 4:
        sum = 0
        for item in array:
            sum += item
        if sum == len(s):
            # 1. 통과
            ip = list()
            p = 0
            for index in array:
                check = s[p:index+p]
                if 0 <= int(check) <= 255:
                    if check[0] == '0' and len(check) > 1:
                        break
                    ip.append(check)
                    p += index
                else:
                    break
            # 남아있는 원소가 없으면 유효한 ip리스트에 추가
            if len(s[p:]) == 0:
                answer.append(".".join(ip))
        return

    array.append(1)
    findIP(array, s)
    array.pop()

    array.append(2)
    findIP(array, s)
    array.pop()

    array.append(3)
    findIP(array, s)
    array.pop()

LeetCode Source