class Solution:

    def valid(self, ns):
        return True if len(ns) and 0 <= int(ns) <= 255 and len(str(int(ns))) == len(ns) else False

    def search(self, ns, depth, prev, ans):
        if depth == 3:
            if self.valid(ns):
                ans.append('.'.join(prev + [ns]))
            return
        for i in range(3):
            if self.valid(ns[:i+1]):
                self.search(ns[i+1:], depth+1, prev + [ns[:i+1]], ans)

    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        self.search(s, 0, [], ans)
        return ans


그냥 별 생각없이 백트래킹함..

함수 여러개 짜는걸 별로 안 좋아하는데 이건 백트래킹 안 쓰는게 더 이상한 코드라


한 번 수정해서 depth 3 넘게 안 가게 짜름 (96ms -> 42ms)