[LeetCode | Python] 93. Restore IP Addresses

느낀점

IP 주소의 구성과 백트랙킹을 구현하는 문제로 그리 어렵지 않게 구현할 수 있다. 주요 포인트는 불필요한 순회를 줄이기 위한 가지치기와 IP주소의 구성을 검증하는 부분일 것 같다.

 

문제

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

 

- 주어진 숫자 문자열 s에 점(.)을 세 번 찍어서 만들 수 있는 모든 유효한 IP 주소를 찾는 문제입니다.

- 유효한 IP 주소는 정확히 네 개의 숫자로 이루어져 있으며, 각 숫자는 0부터 255 사이의 값이어야 하고, 0으로 시작하는 숫자는 허용되지 않습니다 (단, 숫자 자체가 '0'인 경우는 제외).

- 문자열 s의 숫자 순서를 바꾸거나 삭제할 수는 없습니다.

풀이

from typing import List

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        n = len(s)

        def is_valid(segment: str) -> bool:
            return len(segment) == 1 or (segment[0] != '0' and 0 < int(segment) < 256)

        def backtrack(index: int, parts: List[str]):
            if len(parts) == 4:
                if index == n:
                    result.append(".".join(parts))
                return
            if index == n:
                return

            remaining_parts = 4 - len(parts)
            remaining_length = n - index

            if remaining_length < remaining_parts or remaining_length > remaining_parts * 3:
                return

            for length in range(1, min(4, remaining_length + 1)):
                segment = s[index : index + length]
                if is_valid(segment):
                    backtrack(index + length, parts + [segment])

        backtrack(0, [])
        return result

 

결과

• 공간복잡도: $$ O(1) $$
• 시간복잡도: $$ O(N) $$