算法练习Day24 （Leetcode/Python-回溯算法）

93. Restore IP Addresses

A?valid IP address?consists of exactly four integers separated by single dots. Each integer is between?0?and?255?(inclusive) and cannot have leading zeros.

• For example,?"0.1.2.201"?and?"192.168.1.1"?are?valid?IP addresses, but?"0.011.255.245",?"192.168.1.312"?and?"192.168@1.1"?are?invalid?IP addresses.

Given a string?s?containing only digits, return?all possible valid IP addresses that can be formed by inserting dots into?s. You are?not?allowed to reorder or remove any digits in?s. You may return the valid IP addresses in?any?order.

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

思路：分割一个字符串为四段，输出所有满足有效IP地址的分割。分为四段就是切三刀，判断每一段是不是有效，切完三刀后，看第四段是否符合要求，如果还是符合，就输出该结果，否则直接return。

class Solution(object):
    def backtrack(self, s, start_index, point_num, current, result):
        if point_num == 3:
            if self.is_valid(s, start_index, len(s) - 1):
                current += s[start_index:]
                result.append(current)
            return
        for i in range(start_index, len(s)):
            if self.is_valid(s, start_index, i):
                sub = s[start_index:i+1]
                self.backtrack(s,i+1,point_num+1, current+sub+'.', result)

    def is_valid(self, s, start, end):
        if start > end:
            return False
        if s[start] == '0' and start != end:  # 0开头的数字不合法
            return False
        num = 0
        for i in range(start, end + 1):
            if not s[i].isdigit():  # 遇到非数字字符不合法
                return False
            num = num * 10 + int(s[i])
            if num > 255:  # 如果大于255了不合法
                return False
        return True

    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        result = []
        self.backtrack(s, 0, 0, "", result)
        return result

78. Subsets

Given an integer array?nums?of?unique?elements, return?all possible?

subsets

?(the power set).

The solution set?must not?contain duplicate subsets. Return the solution in?any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

思路：列举所有可能的子集。那么所有的子集都是可以在backtrack中被放入result的，而不需要特别的判断了。因为是原数组内无元素重复，所以也不用担心子集重复。

class Solution(object):
    def backtrack(self, nums, start_index, path, result):
        result.append(path[:])
        for i in range(start_index, len(nums)):
            path.append(nums[i])
            self.backtrack(nums, i+1, path, result)
            path.pop()

    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        self.backtrack(nums, 0, [], result)
        return result