LeetCode Day 28 Backtracking Algorithm (4/6)
Published:
Its over half way of backtracking!
Question 1
A valid IP address consists of exactly four integers separated by single dots. Each integer is between
0and255(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
scontaining only digits, return all possible valid IP addresses that can be formed by inserting dots intos. You are not allowed to reorder or remove any digits ins. You may return the valid IP addresses in any order.
It is still a segmentation type of problem, so the solution is recursive. The problem can still be thought of as a tree structure.
We need the variable startIndex because we can’t repeat the split and we need to keep track of where the next level of recursive splitting starts.
We also need the pointNum variable, which records the number of commas added, and is used to determine when the recursion ends.
We can use [startIndex, i] for loop to intercept the substring, and we need to determine whether the substring is legal.
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
result = []
self.backtracking(s, 0, 0, "", result)
return result
def backtracking(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.backtracking(s, i + 1, point_num + 1, current + sub + '.', result)
else:
break
def is_valid(self, s, start, end):
if start > end:
return False
if s[start] == '0' and start != end:
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:
return False
return True
Question 2
Given an integer array
numsof unique elements, return all possiblesubsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
If the process of partitioning this problem, is abstracted to a tree, then what this problem needs is every node of this tree.
class Solution:
def subsets(self, nums):
result = []
path = []
self.backtracking(nums, 0, path, result)
return result
def backtracking(self, nums, startIndex, path, result):
result.append(path[:])
for i in range(startIndex, len(nums)):
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()
Question 3
Given an integer array
numsthat may contain duplicates, return all possiblesubsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
The difference between this question and the previous one is that this one allows for duplicate elements, but the final resultant subset still needs to be de-weighted.
class Solution:
def subsetsWithDup(self, nums):
result = []
path = []
nums.sort()
self.backtracking(nums, 0, path, result)
return result
def backtracking(self, nums, startIndex, path, result):
result.append(path[:])
uset = set()
for i in range(startIndex, len(nums)):
if nums[i] in uset:
continue
uset.add(nums[i])
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()