Day 6

[tech-cow]

Week 2 | Day 6

Goal

DFS / Backtracking

Leetcode

• 301 Remove Invalid Parentheses
• 78. Subsets
• 567. Permutation in String
• 79. Word Search
  • Could Trie improves Speed?
• 126 Word Ladder II
• 721. Accounts Merge
• 10. Regular Expression Matching
  • 变种 regex变成“+”，“*”（我的妈，上来我一看题就知道要挂...我用dp写的，但是天竺小哥说最好用recursion..）

[tech-cow]

301 Remove Invalid Parentheses

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

[tech-cow]

78. Subsets

V1

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)

V2

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()