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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self, s: str):
        # write code here
        res = []
        path = []
        n = len(s)
		# 回溯这里还是索引好用
        def backtrace(start, end):
            if len(path) > 4: # 长度大于4说明太长了
                return
            if len(path) == 4 and start == n: # 这样才正好
                res.append(".".join(path[:]))
            for i in range(start, end): # 起始和终止传进去一个一个找
                cur_s = s[start : i + 1]
                if len(cur_s) > 1 and cur_s[0] == "0": # 超过1位以0为首的不要
                    return
                if 0 <= int(cur_s) <= 255:
                    path.append(cur_s) # 满足条件加入path
                    backtrace(i + 1, end) # 递归，接着找
                    path.pop() # 回溯

        backtrace(0, n)
        return res