Leetcode 93. Restore IP Addresses with Python

문제

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.

Ex. "0.1.2.201" and "192.168.1.1" are valid IP addresses, 
    "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
    
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.

올바른 IP 주소는 "."으로 분리된 4개의 정수로 이루어 진다.
각각의 정수는 0이거나 0으로 시작하지 않는 1~255 사이의 정수여야 한다.
주어진 문자열을 점으로 나누어서 생기는 올바른 IP 주소의 리스트를 리턴하시오.

예시

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

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

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

제한

• 1 <= s.length <= 20
• s 문자열은 오직 숫자로만 이루어져 있다.

풀이법

1. 문자열 사이에 점을 넣는법

A. 문자열의 길이가 4 이상이 아니면 중간에 점을 3개 넣을수 없다

B. 문자열 사이의 공간들을 숫자로 바꾸어 조합을 찾는다.

위와 같은 방식으로 점을 넣어 준 다음 각각 점이 들어간 문자열을 검사해 올바를 경우에만

리스트에 넣어두고 리턴한다.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def ipChecker(ip: str):
            stripped = ip.split(".")
            if len(stripped) != 4: return False
            for s in stripped:
                if s == '0': continue
                if len(s) == 0 or s[0] == '0' or int(s)>255: return False
            return True

        def combination(n: int):
            comb = list()
            for i in range(1, n):
                for j in range(i+1, n):
                    for k in range(j+1, n):
                        comb.append([i, j, k])
            return comb

        if len(s) <= 3: return []

        comb = combination(len(s))
        ans = list()

        for c in comb:
            composite = s[0:c[0]] + '.' + s[c[0]:c[1]] + '.' + s[c[1]:c[2]] + '.' + s[c[2]:]
            if ipChecker(composite):
                ans.append(composite)

        return ans