0093：复原 IP 地址（★）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def check(i,j):
            return j-3<=i<j and (j==i+1 or s[i]!='0') and 0<=int(s[i:j])<=255

        @cache
        def dfs(j,k):
            if k==1:
                return [s[:j]] if check(0,j) else []
            res = []
            for i in range(j):
                if check(i,j):
                    res.extend(sub+'.'+s[i:j] for sub in dfs(i,k-1))
            return res
        return dfs(len(s),4)