算法思想一：栈+哈希表

解题思路：

算法流程
1、构建哈希表 k，其中key为 右括号，value为左括号
2、遍历字符串
    1、判断字符是否在 k.values() 中；
        若在其中则字符入栈；
        否则判断栈是否为空 或者 该字符的 values 是否与 栈顶元素相同；若不同则直接返回 false，若相同则栈顶元素出栈
3、判断栈内元素是否为空，为空则返回 true，反之返回 false

图解：


代码展示：

Python版本 
class Solution:
    def isValid(self , s ):
        # write code here
        # 哈希表
        k = {'}':'{', ')':'(', ']':'['}
        stack = []
        # 遍历字符串
        for a in s:
            if a in k.values():
                stack.append(a)
            elif not stack&nbs***bsp;k[a] != stack.pop():
                return False
        # 如果栈内没有字符则表示 true，反之则 false
        return len(stack) == 0

复杂度分析

时间复杂度O(N)：N表示字符串的长度，遍历字符串
空间复杂度O(N)：最差情况下栈内存储n个字符串，哈希表存储空间

算法思想二：栈

解题思路：

建立一个栈，存储遍历的字符串再进行对比
1、遍历字符串遇到 ‘(’ '[' '{' 左括号，就把相应的右括号（‘)’ ']' '}'）入栈
2、如果遍历遇到右括号 ‘)’ ']' '}' ，则判断是否和栈顶元素相同
    1、不同则直接返回false
    2、相同则将栈顶元素出栈
3、遍历结束判断栈是否为空
图解：

代码展示：

JAVA版本 
import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        Stack<Character>stack = new Stack<Character>();
        for(char c: s.toCharArray()){
            // 碰到左括号，就把相应的右括号入栈
            if(c=='(')stack.push(')');
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');
            // 如果是右括号判断是否和栈顶元素匹配
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        // 最后判断栈中元素是否匹配
        return stack.isEmpty();
    }
}

复杂度分析

时间复杂度O(N)：N表示字符串的长度，遍历字符串
空间复杂度O(N)：最差情况下栈内存储n个字符串