Python traditional backtracking


  • 0

    '''
    class Solution(object):
    def restoreIpAddresses(self, s):

        :type s: str
        :rtype: List[str]
        """
        temp = []
        r = []
        self.dfs(s, temp, r, 0, -1)
        return r
     
    def check(self, s, index, last_pick, i):
        if index != 2:
            if i - last_pick > 1 and s[last_pick + 1] == '0':
                return False
            if int(s[last_pick + 1: i + 1]) <= 255:
                return True
        else:
            if (i - last_pick > 1 and s[last_pick + 1] == '0') or (len(s) - i - 1 > 1 and s[i + 1] == '0'):
                return False
            if int(s[last_pick + 1: i + 1]) <= 255 and int(s[i + 1: len(s)]) <= 255:
                return True
    
    def dfs(self, s, temp, r, index, last_pick):
        if index == 3:
            r.append(s[:temp[0]] + '.' + s[temp[0]: temp[1]] + '.' + s[temp[1]: temp[2]] + '.' + s[temp[2]:])
        else:
            for i in range(last_pick + 1, len(s) - 1):
                if self.check(s, index, last_pick, i):
                    if index >= len(temp):
                        temp.append(i + 1)
                    else:
                        temp[index] = i + 1
                    # print(temp)
                    self.dfs(s, temp, r, index + 1, i)
    

    '''


Log in to reply
 

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