有效的括号

1. 题目描述

给出一个仅包含字符’(‘,’)’,‘{’,‘}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列 括号必须以正确的顺序关闭，“()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]“不合法。

2. 思路

1. 思路一
   • 栈
   • 遍历所有元素，如果是左括号那么入栈，是右括号那么取出栈顶元素看是否和右括号匹配
   • 是否匹配需要一个HashMap
   • 如果最后遍历完且栈为空，那么就是有效的括号序列
2. 思路二
   • 字符串替换

3. 实现

3.1. 栈

var m = map[rune]rune {
    '(':')',
    '[':']',
    '{':'}',
}

func isValid(s string) bool {
    stack := make([]rune, 0)
    for _, r := range []rune(s) {
        if isLeft(r) {
            stack = append(stack, r)
        } else if isRight(r){
            if len(stack) > 0 && isMatch(stack[len(stack)-1], r) {
                stack = stack[:len(stack)-1]
                continue
            }
            return false
        } else {
            return false
        }
    }

    return len(stack) == 0
}

func isLeft(r rune) bool {
    return r == '(' || r == '{' || r == '['
}

func isRight(r rune) bool {
    return r == ')' || r == '}' || r == ']'
}

func isMatch(left, right rune) bool{
    return m[left] == right
}

3.2. 字符串替换

func isValid2(s string) bool {
	if len(s)%2 != 0 {
		return false
	}

	flag := true
	for flag {
		oldLength := len(s)
		s = strings.Replace(s, "()", "", -1)
		s = strings.Replace(s, "{}", "", -1)
		s = strings.Replace(s, "[]", "", -1)

		if len(s) == oldLength {
			flag = false
		}
	}

	return len(s) == 0
}

4. 参考

• 括号序列_牛客题霸_牛客网
• 有效的括号（辅助栈法，极简+图解） - 有效的括号 - 力扣（LeetCode）