[leetcode] 20/22 Vaild parenthe

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true

括号匹配

使用 stack FIFO 的特点实现

1. 如果stack 为空 或者 当前字符为 左括号， 入栈
2. 其余情况 ， 出栈 （ 这里有3类括号，所以出栈前要比较一下 栈顶和当前字符是否匹配 ）

#include <stack>
#include <unordered_map>
using namespace std;
class Solution {
public:
    bool isValid(string s) {
        stack<char> _stack;
        unordered_map<char,char> up={
            {'(',')'},
            {'{','}'},
            {'[',']'}
        };
        
        for(char _s:s){
            
            if(_stack.empty() || up[_s]){
                _stack.push(_s);
                continue;
            }
            if(!up[_s]){
                
                if(up[_stack.top()] != _s){
                    return false;
                }
                _stack.pop();
                
            }
        }
        return _stack.empty();
    }
};

image.png

生成括号

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:

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

这题是 组合+ 括号匹配。
当然你可以列出所有可能的组合 然后调用上题来输出所有有效的括号。
比如这样

from collections import deque

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        #括号匹配验证
        def isVaild(s):
            deq= deque(s)
            stack= []
            while deq:
                if not stack or stack[-1] ==")":
                    stack.append(deq.popleft())
                else:
                    cur = deq.popleft()
                    if cur ==')':
                        stack.pop()
                    else:
                        stack.append(cur)
            return stack==[]
        

        str_len = 2*n
        res=[]
        # 递归 长度为6 的() 所有组合 
        def rec(temp,cur):
            if cur == str_len:
                res.append(temp)
            else:
                rec(temp+"(",cur+1)
                rec(temp+")",cur+1)
        
        rec("",0)
        # 输出所有有效括号
        ans=[]
        for i in res:
            if isVaild(i):
                ans.append(i)
        return ans
                  

image.png

居然能跑出来， 说明这个复杂度只是有点高， 因为递归过程中有很多可以分支可以提前结束。

因此， 这里我们选择递归组合的过程中剪枝。
具体怎样剪枝呢， 其实就2点：

1. 第一个字符肯定是"("
   2.当 右边括号用的比 左边的多时， 直接可以判定为无效。
   这里画了了例子。

   
   image.png

代码：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        _generateParenthesis(n-1,n,"(");
        return _ans;
    }
    
    
private:
    vector<string> _ans;
    
    void _generateParenthesis(int a, int b,string pa){
        
        // 剪枝
        if(a>b){
            return;
        }
        
        if( !a && !b){
            _ans.push_back(pa);
            return;
        }
        
        if (a>0){
            _generateParenthesis(a-1,b,pa+"(");
        }
        
        if(b>0){
            _generateParenthesis(a,b-1,pa +")");
        }
        
        
    }
};

image.png

这题 前段时间面试的时候遇到一脸懵逼， 哎 -_- : 果然不刷leetcode去面试就是找虐。。。