class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
ans = []
self.helper(ans, s, 4, [])
return ['.'.join(x) for x in ans]
def helper(self, ans, s, k, temp):
if len(s) > k*3:
return
if k == 0:
ans.append(temp[:])
else:
for i in range(min(3,len(s)k+1)):
if i==2 and int(s[:3]) > 255 or i > 0 and s[0] == '0':
continue
self.helper(ans, s[i+1:], k1, temp+[s[:i+1]])
DFS in Python


@bdeng3 We need to ensure that there are sufficient digits to fill all 4 digit groups and prevent the recursion entering those useless paths during dfs.
Suppose we have the input string '1111', we are going to only have '1' in our first digit group and in the first dfs level we are not going to have '11' or more because if we get '11' in first digit area, it is not possible for us to have sufficient digits to fill all four groups after that.

@lilixu Hi, thanks for your quick reply! I understand that this condition is used to set a limit to how many digits should be placed in each group. But I'm just curious how do you get this function
len(s)  k + 1
. I was thinking in this way:len(s)  k + 1 = len(s) (k1)
, whereas(k1)
is somehow related to the number of digit groups left? Many thanks if you can share your insight with us

@bdeng3 In order to ensure sufficient string length for the unfilled digit groups, each digit group should be at least filled with one digit. On each level, we have a remaining string of length len(s) and k groups to be filled.
As required,
len(s)  str_length_to_take_in_this _level >= k  1
(we need to deduct 1 (this digit group) from k)
So we have
1 <= str_len_to_take <= len(s)  (k  1)
(Each digit group should at least have one digit)
in python
range(1, len(s) (k1) + 1)
, which isrange(len(s)k+1)
if you write i+1 in the loop content...

Similar idea with regex
from re import match vre = [r'[09]', r'[19][09]', r'1[09][09]2[04][09]25[05]'] class Solution(object): def restoreIpAddresses(self, s): possible = lambda s: (match(regx, s).group() for regx in vre if match(regx, s)) def helper(s, depth): if not depth: return [] if s else [[]] return [[p]+r for p in possible(s) for r in helper(s[len(p):], depth1)] return map('.'.join, helper(s, 4))