Day 5 | 2/20/20

[tech-cow]

Goal

• Focus on High Freq Qs

• 560. Subarray Sum Equals K
• 301. Remove Invalid Parentheses
• 20. Valid Parentheses
• 921. Minimum Add to Make Parentheses Valid
• 1249. Minimum Remove to Make Valid Parentheses
• 98. Validate Binary Search Tree (x5)

[tech-cow]

560. Subarray Sum Equals K

'''
不懂的可以参考: https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/hot-100-he-wei-kde-zi-shu-zu-python3-cong-bao-li-j/
[1:29] Start

Thought Process
1. [Brute Force]

for i -> n
    for j -> (i, n)
        find sum of nums[i:j + 1] == target

Time: O(N^3)


2. PreSum

for i -> n
    preSum = [0] * len(arr)
    for j -> (i, n):
        if preSum[j] - preSum[i] == k
            add to res

Time: O(N^2)


3. preSum

because: preSum[j] - preSum[i] == k

so: preSum[i] == preSum[j] - k

because we always iterate i before j
we store preSum[i] in hash
and while we iterate J, we do preSum[j] - k, and see if it's in hash.

Time: O(N)

'''

# preSum + O(N^2)
class Solution(object):
    def subarraySum(self, nums, target):
        if not nums: return 0
        n = len(nums)
        res = 0
        for i in range(n):
            preSum = 0
            for j in range(i, n):
                preSum += nums[j]
                if preSum == target:
                    res += 1
        return res

# preSum + hash O(N)
class Solution(object):
    def subarraySum(self, nums, target):
        if not nums: return 0
        dic = {0 : 1}
        preSum = 0
        res = 0
        for i in range(len(nums)):
            preSum += nums[i]
            if preSum - target in dic:
               res += dic[preSum - target]
            dic[preSum] = dic.get(preSum, 0) + 1   
        return res

[tech-cow]

301. Remove Invalid Parentheses (X8)

'''
[8:28] Start

出现重大Bug: DFS加层的时候，index没有＋1  ！！！！！
'''

class Solution:
    def removeInvalidParentheses(self, s):
        leftRemain, rightRemain = self.calDiff(s)
        curLeft, curRight = 0, 0
        res = set()
        self.dfsHelper(s, curLeft, curRight, leftRemain, rightRemain, res, 0, "")
        return list(res)
        
        
    def dfsHelper(self, s, curLeft, curRight, leftRemain, rightRemain, res, index, temp):
        #Base:
        if index == len(s) and curLeft == curRight and leftRemain == rightRemain == 0:
            res.add(temp)
            return
    
        if index < len(s):
            if s[index] == "(":
                if leftRemain:
                    self.dfsHelper(s, curLeft, curRight, leftRemain - 1, rightRemain, res, index + 1, temp)  #删'('
                self.dfsHelper(s, curLeft + 1, curRight, leftRemain, rightRemain, res, index + 1, temp + '(')  #不删'('

            elif s[index] == ")":
                if rightRemain:
                    self.dfsHelper(s, curLeft, curRight, leftRemain, rightRemain - 1, res, index + 1, temp)  #删')'
                if curRight < curLeft:
                    self.dfsHelper(s, curLeft, curRight + 1, leftRemain, rightRemain, res, index + 1, temp + ')')  #不删')'

            else: # "a...z and other cases"
                self.dfsHelper(s, curLeft, curRight, leftRemain, rightRemain, res, index + 1, temp + s[index])

    
    def calDiff(self, s):
        leftRemain, rightRemain = 0, 0
        for ch in s:
            if ch == '(':
                leftRemain += 1
            if ch == ')':
                if leftRemain != 0:
                    leftRemain -= 1
                else:
                    rightRemain += 1
        return leftRemain, rightRemain

[tech-cow]

20. Valid Parentheses

# 重大BUG: 没有思考 Stack == [] 而且，没有popstack，干
class Solution(object):
    def isValid(self, s):
        if not s: return True
        dic = {'(' : ')' , '{' : '}' , '[' : ']'}
        
        stack = []
        
        for ch in s:
            if not stack:
                if ch in dic:
                    stack.append(ch)
                else:
                    return False
            else:
                if ch in dic:
                    stack.append(ch)
                else:
                    if ch != dic[stack.pop()]:
                        return False
        return stack == []

[tech-cow]

921. Minimum Add to Make Parentheses Valid

class Solution(object):
    def minAddToMakeValid(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]

32. Longest Valid Parentheses

Brute Force | Bug-free

class Solution(object):
    def longestValidParentheses(self, s):
        n = len(s)
        globalMax = float('-inf')
        for i in range(n):
            if s[i] == ')': continue
            for j in range(i, n):
                subStr = s[i : j + 1]
                if self.isValid(subStr):
                    globalMax = max(globalMax , len(subStr))
        return globalMax if globalMax != float('-inf') else 0
                    
    
    def isValid(self, S):
        leftDiff, rightDiff = 0, 0
        for ch in S:
            if ch == '(':
                leftDiff += 1
            else:
                if leftDiff != 0:
                    leftDiff -= 1
                else:
                    rightDiff += 1
        return True if leftDiff + rightDiff == 0 else False

[tech-cow]

1249. Minimum Remove to Make Valid Parentheses

class Solution(object):
    def minRemoveToMakeValid(self, S):
        indexToDel = set()
        self.getIndex(S, indexToDel)
        res = ''
        for i, ch in enumerate(S):
            if i not in indexToDel:
               res += ch
        return res

    
    def getIndex(self, S, indexToDel):
        stack = []    
        for i, ch in enumerate(S):
            if ch not in '()': continue

            if ch == '(':
                stack.append(i)
            
            elif ch == ')':
                if not stack:
                    indexToDel.add(i)
                else:
                    stack.pop()
        
        # 处理最后留下来的左括号
        if stack:
            for index in stack:
                indexToDel.add(index)

A bit faster

class Solution(object):
    def minRemoveToMakeValid(self, s):
        leftIndex, rightIndex = [], []
        for i, ch in enumerate(s):
            if ch == '(':
                leftIndex.append(i)
            elif ch == ')':
                if len(leftIndex) == 0:
                    rightIndex.append(i)
                else:
                    leftIndex.pop()
        indexToDel = set(leftIndex + rightIndex)
        
        res = []
        for i, ch in enumerate(s):
            if i not in indexToDel:
               res.append(ch)
        return ''.join(res)