华为OD面试手撕算法-合法的括号对_华为od cpp面试手撕代码

 题目描述

本题为leetcode原题(简单难度)：有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

解题思路

【栈 + 哈希表】

1. 构造存储括号对<key为右括号，val为左括号>的哈希表；

2. 栈操作：

        1）若当前元素为左括号，直接入栈，继续遍历下一个元素；

        2）若当前元素为右括号，基于map判断其是否与栈顶元素相匹配？

                ①不匹配：直接返回false；

                ②匹配：栈顶元素出栈，继续遍历下一个元素；

遍历完成后，判断栈是否为空：

        若为空，返回true；否则返回false

代码实现

Golang代码实现如下

func isValid(s string) bool {
    //思路：使用栈 + map 完成字符串匹配
    matchMap := map[byte]byte{
        ')': '(',
        ']': '[', 
        '}': '{',
    }
    stack := list.New()
    for _,c := range s {
        if c == '(' || c == '[' || c == '{' {
            //左括号：直接入栈
            stack.PushBack(byte(c))
        }else if stack.Len() > 0 && stack.Back().Value.(byte) == matchMap[byte(c)] {
            //右括号：判断是否与栈顶的左括号匹配
            stack.Remove(stack.Back())
        }else{
            return false
        }
    }
    return stack.Len() == 0
}