Parentheses

check if valid, 須考慮 ')' 在開頭的情況, 遞歸時也要考慮 ’(‘ 個數大於 ’)' 個數

20. Valid Parentheses

def isValid(self, s: str) -> bool:
    dic = {')':'(', ']':'[', '}':'{'}
    stack = []
    
    for c in s:
        if c in dic:
            left = '#' if not stack else stack.pop()
            if left != dic[c]:
                return False
        else:
            stack.append(c)
            
    return not stack

678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.

2. Any right parenthesis ')' must have a corresponding left parenthesis '('.

3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.

4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.

5. An empty string is also valid

 """
Count the lower bound and higher bound of left bracket
If higher bound < 0, means it can't be valid in current position and afterward
Check if lower bound == 0 when return
"""
def checkValidString(self, s: str) -> bool:
    lo, hi = 0, 0
    
    for c in s:
        lo += 1 if c == '(' else -1
        hi += 1 if c in '(*' else -1
        if hi < 0: return False
        if lo < 0: lo = 0
            
    return lo == 0

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

n = 3
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

 def generateParenthesis(self, n: int) -> List[str]:
    ans = []
    
    def backtracking(s, left, right):
        if len(s) == 2*n:
            ans.append(s)
            return
        if left < n:
            backtracking(s+'(', left+1, right)
        if right < left:
            backtracking(s+')', left, right+1)
            
    backtracking('', 0, 0)
    
    return ans         

32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

dp

1. State: dp[i], s[:i+1]的LVP

2. Tran: only consider s[i] == ')', dp[i] = dp[i-2] + 2 if s[i-1] == '(' dp[i] = dp[i-dp[i-1]-1] + 2 if s[i-1] = ')' + dp[i-dp[i-1]-2] if i-dp[i-1]-2 >= 0

def longestValidParentheses(self, s: str) -> int:    
    dp = [0] * len(s)
    ans = 0

    for i in range(1, len(s)):
        if s[i] == ')':
            if s[i-1] == '(':
                dp[i] = 2 + (dp[i-2] if i-2 >= 0 else 0)
            elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
                dp[i] = 2 + dp[i-1]
                if i-dp[i-1]-2 >= 0:
                    dp[i] += dp[i-dp[i-1]-2]

        ans = max(ans, dp[i])
    return ans

List double end traverse

There are only three cases for a string:

1. '(' are more than ')'

2. '(' are less than ')'

3. '(' and ')' are the same

Now, when you scan from left to right, you can only find the correct maxLength for cases 2 and 3, because if it is case 1, where '(' are more than ')' (e.g., "((()"), then left is always greater than right and maxLength does not have the chance to be updated.

 def longestValidParentheses(self, s: str) -> int: 
    left, right = 0, 0 ans = 0
    for c in s:
        if c == '(': left+=1
        else: right+=1

        if left == right:
            ans = max(ans, right*2)
        elif right > left:
            left, right = 0, 0


    left, right = 0, 0
    for c in s[::-1]:
        if c == '(': left+=1
        else: right+=1

        if left == right:
            ans = max(ans, right*2)
        elif left > right:
            left, right = 0, 0

    return ans

1190. Reverse Substrings Between Each Pair of Parentheses

You are given a string s that consists of lower case English letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Input: s = "(abcd)"
Output: "dcba"

Time: O(n^2), Space: O(n)

def reverseParentheses(self, s: str) -> str:
    line = ''
    stack = []
    
    for c in s:
        if c == '(':
            stack.append(line)
            line = ''
        elif c == ')':
            pre = stack.pop()
            pre += line[::-1]
            line = pre
        else:
            line += c
            
    return line

Time: O(n) for 2 passes, see Lee's explanation

921. Minimum Add to Make Parentheses Valid

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

def minAddToMakeValid(self, S: str) -> int:
    balance = 0
    count = 0

    for c in S:
        balance += 1 if c == '(' else -1

        # right bracket is greater, must add a left bracket
        if balance == -1:
            count += 1
            balance = 0
                  # rest of left brackets
    return count + balance

1249. Minimum Remove to Make Valid Parentheses

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or

• It can be written as AB (A concatenated with B), where A and B are valid strings, or

• It can be written as (A), where A is a valid string.

  """
  record the index should be removed and rebuild the string
  """
  def minRemoveToMakeValid(self, s: str) -> str:
    stack = [] # record left parentheses to remove
    remove = set() # record right parenthesese to remove
    
    for i, c in enumerate(s):
        if c not in '()': continue
        if c == '(':
            stack.append(i)
        # "))((" 的情況
        elif c == ')' and not stack:
            remove.add(i)
        else:
            stack.pop()
            
    remove = remove.union(set(stack))
    
    build = ''
    for i in range(len(s)):
        if i not in remove:
            build += s[i]
            
    return build

301. Remove Invalid Parentheses

example

Input: "()())()"
Output: ["()()()", "(())()"]

1. 先計算 需要remove 多少 '(' and ')'

2. Backtracking, 適當剪支, 符合條件加入答案(利用set, 因為可能重複)

def removeInvalidParentheses(self, s: str) -> List[str]:
    # count invalid '(' and ')'

    left, right = 0, 0
    for c in s:
        if c == '(':
            left += 1
        elif c == ')':
            if left == 0:
                right += 1
            else:
                left -= 1

    self.ans = set()
    self.dfs(s, 0, 0, 0, left, right, '')
    return list(self.ans)


def dfs(self, s, idx, l, r, left_rem, right_rem, exp):
    if idx == len(s):
        if left_rem == right_rem == 0:
            self.ans.add(exp)
        return

    c = s[idx]
    #  ignore c either keep c 分開討論
    if c == '(':
        self.dfs(s, idx+1, l+1, r, left_rem, right_rem, exp+c)
        if left_rem > 0:
            self.dfs(s, idx+1, l, r, left_rem-1, right_rem, exp)
    elif c == ')':
        # prune, 只有 r < l 才進行 recursion
        if l > r:
            self.dfs(s, idx+1, l, r+1, left_rem, right_rem, exp+c)
        if right_rem > 0:
            self.dfs(s, idx+1, l, r, left_rem, right_rem-1, exp)
    # c is letter        
    else:
        self.dfs(s, idx+1, l, r, left_rem, right_rem, exp+c)