题解 | #数字字符串转化成IP地址#

#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s ):
        # write code here
        if len(s) < 4 or len(s) > 12: return []
        res, tmp = [], []
        def backtrack(idx):
            if len(tmp) == 4 and idx == len(s):
                res.append('.'.join(tmp))
            for i in range(1, 4):
                if idx+i > len(s): continue
                sub = s[idx:idx+i]
                if len(sub) > 1 and sub[0] == '0': continue
                if int(sub) > 255: continue
                tmp.append(sub)
                backtrack(idx+i)
                tmp.pop()
        backtrack(0)
        return res