DFS in Python

  • 8
    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:
            if k == 0:
                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':
                    self.helper(ans, s[i+1:], k-1, temp+[s[:i+1]])

  • 0

    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.

  • 0

    @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.

  • 0

    @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

  • 1

    @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)- (k-1) + 1) , which is range(len(s)-k+1) if you write i+1 in the loop content...

  • 0

    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))

  • 0

    Thank you. Its iterative version can sometimes beat 100% python submission:

    class Solution(object):
        def restoreIpAddresses(self, s):
            while S:
                if len(l)==4:
                    if not s: 
                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':
                        if s[0]=='0': break
            return res

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.