def restoreIpAddresses(self, s):
ret = []
self.dfs(ret, s, [], 0, 0)
return ret
def dfs(self, ret, s, path, index, depth):
if depth == 4 and index == len(s):
ret.append('.'.join(path))
return ret
if index >= len(s) or depth >= 4:
return
for i in range(index, max(index+3,len(s))):
t = s[index:i+1]
if t[0] == '0' and t != '0':
continue
if 255 >= int(t) >= 0:
self.dfs(ret, s, path+[t], i+1, depth+1)
AC python code, easyunderstanding, follow the backtracking code template


Also you don't need depth
class Solution(object): def dfs(self, ans, s, chosen, left): if (len(chosen) == 4 and left == len(s)): ans.append('.'.join(chosen)) elif len(chosen) < 4: for right in range(left, min(left+3, len(s))): choose = s[left:right+1] if (int(choose) <= 255 and (len(choose) == 1 or choose[0] != '0')): self.dfs(ans, s, chosen + [choose], right+1) def restoreIpAddresses(self, s): ans = [] chosen = [] self.dfs(ans, s, chosen, 0) return ans