1.题目

括号匹配

2.题解与代码

这是一道栈的典型例题
根据栈的特性，现金后出
可以想到一个思路：
“(){}[]” 但匹配到左半部分括号的时候，入栈，遍历字符串遇到其他的判断栈的最后一个元素是不是当前遍历的元素，不是返回False,或者相等的话进入另一个分支，弹栈。

2.1纯栈

python版

# 代码冗余，但方便理解
# 纯栈
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        flag = False
        for element in s:
            if element=="(":
                stack.append(")")
            elif element=="[":
                stack.append("]")
            elif element=="{":
                stack.append("}")
            # 另一半部分，要进行与栈的最后一个元素匹配
            elif element==")":
                if not stack:
                    return False
                if stack.pop()!=")":
                    return False
            elif element=="]":
                if not stack:
                    return False
                if stack.pop()!="]":
                    return False
            elif element=="}":
                if not stack:
                    return False
                if stack.pop()!="}":
                   return False
        if stack:
            return False
        return True
# 优化
def isValid(self, s: str) -> bool:
        stack = []
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            # 这一句代表的是上面匹配右半部分括号的部分
            # 如果是空栈或者最后一个元素不等于当前遍历的
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
        return True if not stack else False

go版

func isValid(s string) bool {
    if len(s)==0{
        return true
    }
    stack := []byte{}
    for _,vv:=range s{
        v := byte(vv)
        if v=='('{
            stack = append(stack, ')')
        }else if v=='['{
            stack = append(stack, ']')
        }else if v=='{'{
            stack=append(stack, '}')
        }else if len(stack)==0||stack[len(stack)-1]!=v{
            // 这里面的意思是，如果匹配到一半，栈里面没了，不行，或者当前遍历的元素不等于栈顶元素
            return false
        }else{
            // 剩下的情况都是能匹配上，只需弹栈
            stack = stack[:len(stack)-1]
        }
    }
    // 如果这时候栈不为空那么false'
    if len(stack)!=0{
        return false
    }
    return true
}

2.2hash表

go版

// hash表
func isValid(s string) bool {
    m := map[byte]byte{'(': ')', '[': ']', '{': '}'}
    stack := []byte{}
    if len(s) == 0 {
        return true
    }
    for _, v := range s {
        // 要记得转化类型，不然v是int32
        if _, ok := m[byte(v)]; ok {
            stack = append(stack, m[byte(v)])
        } else if len(stack) == 0 || stack[len(stack)-1] != byte(v) {
            return false
        } else {
            stack = stack[:len(stack)-1]
        }

    }
    if len(stack)!=0{
        return false
    }
    return true
}

python版

# python 实现
def isValid(self, s: str) -> bool:
        stack = []
        mapping = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        for item in s:
            if item in mapping.keys():
                stack.append(mapping[item])
            elif not stack or stack[-1] != item: 
                return False
            else: 
                stack.pop()
        return True if not stack else False