Restore IP Addresses

• 그냥 완전 탐색으로 모든 경우의 수를 다 찾아봐야 한다.
  • 만약 가능한 address의 갯수를 세는 거라면 DP로 풀 수 있다.
• address를 만드는 가능한 방법의 수는, 각 숫자는 1~3자리로 끊을 수 있고, 숫자의 갯수는 4개이므로, 총 갯수는 3^4. 굉장히 작다
  • 따라서 시간 복잡도는 인풋의 길이와 관계 없이 그냥 O(1)이다
• 보통 이런식의 완전 탐색을 재귀함수로 구현해서 풀 때, 한 단계 들어갈 때마다 substring을 새로 만들어서 다음 단계로 넘겨주는 방식으로 짜게 되면, 객체가 계속 새로 생성되므로 메모리 부족과 시간 낭비를 겪게 된다. 그래서 substring을 만드는 대신 index만 갱신해서 넘기곤 하지만, 이 문제에서는 탐색 깊이가 4밖에 안되므로 그냥 막 짜도 상관없다
• 그리고 탐색 깊이가 4밖에 안된다는 것은 그냥 무식하게 4중 포문으로 짜는 것도 가능하다는 의미. 사실 속도는 그 편이 가장 빠를 것이다.
• 실제 구현은 4중 포문..보다는 조금 덜 무식한 (그러나 덜 최적화된) 방식의 iterative 버전과, 정석적인 recursive 버전으로 해봤는데.. iterative 버전은 최적화에서 상당히 거리가 멀게 짜여졌음에도 더 빨리 돌았다.
  • iterative 코드: 24ms / recursive 코드: 44ms

"""Solution code for "LeetCode 93. Restore IP Addresses". (Non-recursive
version)

- Problem link: https://leetcode.com/problems/restore-ip-addresses/
- Solution link: http://www.teferi.net/ps/problems/leetcode/93
"""


import itertools


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ip_list = []
        for lengths in itertools.product([1, 2, 3], repeat=4):
            if sum(lengths) != len(s):
                continue
            numbers = []
            beg = 0
            for l in lengths:
                number = s[beg:beg + l]
                if (number[0] == '0' and l > 1) or int(number) > 255:
                    break
                numbers.append(number)
                beg += l
            else:
                ip_list.append('.'.join(numbers))

        return ip_list

"""Solution code for "LeetCode 93. Restore IP Addresses".

- Problem link: https://leetcode.com/problems/restore-ip-addresses/
- Solution link: http://www.teferi.net/ps/problems/leetcode/93
"""


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def solveRec(numbers, s):
            if len(numbers) == 4:
                if not s:
                    ip_list.append('.'.join(numbers))
                return

            for l in range(1, 4):
                if l > len(s):
                    break
                number = s[:l]
                if int(number) <= 255:
                    solveRec(numbers + [number], s[l:])
                if s[0] == '0':
                    break

        ip_list = []
        solveRec([], s)
        return ip_list