[Python] LeetCode - Restore IP Addresses

https://leetcode.com/problems/restore-ip-addresses/

Restore IP Addresses - LeetCode

# 확실히 재귀가 코드 진행상황이 직관적으로 보이거나 와닿지가 않아서 힘든 것 같다..

 

 

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s) < 4:
            return []
        answer = []
        IPs = []
        def valid(string):
            if len(string) == 1:
                return True
            if int(string) > 255 or string[0] == '0':
                return False
            return True
        
        def BT(index, ip):
            # 종료 조건
            if len(ip) > 4:
                return
            elif index == len(s) and len(ip) == 4:
                res = '.'.join(ip)
                answer.append(res)
                return
            
            idx = index + 3
            for i in range(index, min(len(s), idx)):
                num_str = s[index: i + 1]
                # 유효성 검사
                if valid(num_str):
                    IPs.append(num_str)
                    # 재귀 호출
                    BT(index + len(num_str), IPs)
                    IPs.pop()
        
        ip = []
        BT(0, ip)
        return answer