22. Generate Parentheses 

dfs stack

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

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路：

If you have two stacks, one for n "(", the other for n ")", you generate a binary tree from these two stacks of left/right parentheses to form an output string.

This means that whenever you traverse deeper, you pop one parentheses from one of stacks. When two stacks are empty, you form an output string.

How to form a legal string? Here is the simple observation:

• For the output string to be right, stack of ")" most be larger than stack of "(". If not, it creates string like "())"
• Since elements in each of stack are the same, we can simply express them with a number. For example, left = 3 is like a stacks ["(", "(", "("]

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        left, right, res = n, n, []
        self.dfs(left, right, res, "")
        return res
    
    
    def dfs(self, left, right, res, cur):
        if left > right:
            return
        
        if not left and not right:
            res.append(cur)
            
        if left:
            self.dfs(left-1, right, res, cur+'(')
        if right:
            self.dfs(left, right-1, res, cur+')')

678. Valid Parenthesis Strin

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.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

思路：

The number of open parenthesis is in a range [cmin, cmax]
cmax counts the maximum open parenthesis, which means the maximum number of unbalanced '(' that COULD be paired.
cmin counts the minimum open parenthesis, which means the number of unbalanced '(' that MUST be paired.

The string is valid for 2 condition:

1. cmax will never be negative.
2. cmin is 0 at the end.

不是很懂

 

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        cmin = cmax = 0
        for c in s:
            if c == '(':
                cmax += 1
                cmin += 1
            if c == ')':
                cmax -= 1
                cmin = max(cmin-1, 0)
            if c == '*':
                cmax += 1
                cmin = max(cmin-1, 0)
            if cmax < 0:
                return False
        return cmin == 0

32. Longest Valid Parentheses 

这个article写得很好， 这种括号的一般都可以用stack来做

https://leetcode.com/articles/longest-valid-parentheses/

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        # left right O(n) O(1)
        n = len(s)
        maxLen = 0
        left = right = 0
        
        for i in xrange(n):  # 从左往右
            if s[i] == '(':
                left += 1
            elif s[i] == ')':
                right += 1
            
            if left == right:
                maxLen = max(maxLen, left*2)
            
            if right > left:
                left = right = 0
        
        left = right = 0
        for i in xrange(n-1, -1, -1):  # 从右往左 重复
            if s[i] == '(':
                left += 1
            elif s[i] == ')':
                right += 1
            
            if left == right:
                maxLen = max(maxLen, left*2)
            
            if right < left:  # 反过来
                left = right = 0
                
        return maxLen