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': continue self.helper(ans, s[i+1:], k-1, temp+[s[:i+1]])
May I ask how did you get
len(s) - k + 1？ I knew that this is related to how many digits in one number from IP address. But it seems confusing to me on how to understand this.
@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) -(k-1), whereas
(k-1) 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.
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)
range(1, len(s)- (k-1) + 1) , which is
range(len(s)-k+1) if you write i+1 in the loop content...
Similar idea with regex
from re import match vre = [r'[0-9]', r'[1-9][0-9]', r'1[0-9][0-9]|2[0-4][0-9]|25[0-5]'] 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):], depth-1)] return map('.'.join, helper(s, 4))
Thank you. Its iterative version can sometimes beat 100% python submission:
class Solution(object): def restoreIpAddresses(self, s): res= S=[(,s)] while S: l,s=S.pop() if len(l)==4: if not s: res.append('.'.join(l)) elif len(s)<=(4-len(l))*3: for i in range(min(3,len(s)-3+len(l))): if i!=2 or s[:3] <= '255': S.append((l+[s[:i+1]],s[i+1:])) if s=='0': break return res
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.