leetcode medium : Restore IP Addresses

전체탐색 문제

Restore IP Addresses - LeetCode

Restore IP Addresses - LeetCode

 

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        
        def dfs(path, remaining):

            #끊어낸 숫자가 4개면 탐색을 종료해야함
            if len(path) == 4:
                if not remaining:
                    result.append('.'.join(path))
                return

            

            #1~3개씩 끊어서 유효성 검사 수행

            #range의 두번째 인자는 남은 문자열이 3개 미만일 경우를 고려한 것
            for i in range(1, min(len(remaining),3)+1):
                s = remaining[:i]
                if int(s) <= 255 and (len(s) == 1 or s[0] != '0'):
                    dfs(path + [s], remaining[i:])
        
        dfs([], s)
        return result

 

1~3개씩 숫자를 끊어보고 유효하면 남은 문자열에 대해 탐색을 재귀적으로 수행한다.