Easy to understand, python recursive solution


  • 1
    F
    class Solution(object):
        def restoreIpAddresses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            if len(s) > 12: return []
            Solution.res = []
            self.genIp(s, "", 0, 0, 0)
            return Solution.res
        # cur: the candidate string
        # val: the value of the current section
        # pos: position of s
        # n: how many '.' have we added
        def genIp(self, s, cur, val, pos, n):
            if val > 255: return
            if n == 4 and pos == len(s):
                Solution.res.append(cur[:-1])
                return
            val = 0
            for i in xrange(1, min(4, len(s)+1-pos)):
                num = s[pos: pos+i]
                val = 10*val + ord(s[pos + i - 1]) - ord('0')
                # Skip positive nums that start with 0 or numbers like 000
                if i > 1 and num[0] == '0': return
                self.genIp(s, cur + num + '.', val, pos + i, n+1)

Log in to reply
 

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