Python solution with detailed explanation


  • 0
    G

    Solution

    Restore IP Addresses https://leetcode.com/problems/restore-ip-addresses/

    • Simple solution - straightforward use of backtracking.
    • One corner case - we cannot have "010" or "001". Add code to test that while generating candidates.
                if i + 1 < len(s) and s[i] != "0":
                    candidates.append(s[i:i+2])
                if i + 2 < len(s) and int(s[i:i+3]) <= 255 and s[i:i+3].startswith("00") == False and s[i:i+3].startswith("0") == False:
                    candidates.append(s[i:i+3])
    
    class Solution(object):
        def helper(self, i, s, so_far, result):
            if len(so_far) == 4:
                if i >= len(s):
                    result.append(".".join(so_far))
                elif i < len(s):
                    return
            elif i == len(s):
                return
            else:
                candidates = [s[i]]
                if i + 1 < len(s) and s[i] != "0":
                    candidates.append(s[i:i+2])
                if i + 2 < len(s) and int(s[i:i+3]) <= 255 and s[i:i+3].startswith("00") == False and s[i:i+3].startswith("0") == False:
                    candidates.append(s[i:i+3])
                for c in candidates:
                    so_far.append(c)
                    self.helper(i+len(c), s, so_far, result)
                    so_far.pop()
            return
        
        def restoreIpAddresses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            result = []
            self.helper(0, s, [], result)
            return result
    

Log in to reply
 

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