Open tech-cow opened 4 years ago
class Solution(object):
def removeInvalidParentheses(self, s):
leftDiff, rightDiff = self.calDiff(s)
res = set()
self.dfsHelper(s, 0, 0, leftDiff, rightDiff, 0, '', res)
return list(res)
def dfsHelper(self, s, leftCounter, rightCounter, leftDiff, rightDiff, index, temp, res):
#base
if index == len(s):
if leftCounter == rightCounter and leftDiff == rightDiff == 0:
res.add(temp)
return
else:
if s[index] == "(":
if leftDiff > 0:
self.dfsHelper(s, leftCounter, rightCounter, leftDiff - 1, rightDiff, index + 1, temp, res)
self.dfsHelper(s, leftCounter + 1, rightCounter, leftDiff, rightDiff, index + 1, temp + '(', res)
elif s[index] == ")":
if rightDiff > 0:
self.dfsHelper(s, leftCounter, rightCounter, leftDiff, rightDiff - 1, index + 1, temp, res)
if rightCounter < leftCounter:
self.dfsHelper(s, leftCounter, rightCounter + 1, leftDiff, rightDiff, index + 1, temp + ')', res)
else: # a-z any other characters
self.dfsHelper(s, leftCounter, rightCounter, leftDiff, rightDiff, index + 1, temp + s[index], res)
def calDiff(self, s):
leftDiff, rightDiff = 0, 0
for ch in s:
if ch == "(":
leftDiff += 1
elif ch == ")":
if leftDiff != 0:
leftDiff -= 1
else:
rightDiff += 1
return leftDiff, rightDiff
class Solution(object):
def subsets(self, nums):
if not nums: return []
res = []
self.dfsHelper(nums, [], res, 0)
return res
def dfsHelper(self, nums, temp, res, index):
if index == len(nums):
res.append(temp[:])
return
temp.append(nums[index])
self.dfsHelper(nums, temp, res, index + 1)
temp.pop()
self.dfsHelper(nums, temp, res, index + 1)
class Solution(object):
def subsets(self, nums):
if not nums: return []
res = []
self.dfsHelper(nums, [], res, 0)
return res
def dfsHelper(self, nums, temp, res, depth):
res.append(temp[:])
for i in range(depth, len(nums)):
temp.append(nums[i])
self.dfsHelper(nums, temp, res, i + 1)
temp.pop()
Week 2 | Day 6
Goal
DFS / Backtracking
Leetcode