0020.valid-parentheses.md

0020.Valid-Parentheses

Description

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. 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

Tags: Stack, String

题解

思路1

题意是判断括号匹配是否正确，很明显，我们可以用栈来解决这个问题，当出现左括号的时候入栈，当遇到右括号时，判断栈顶的左括号是否何其匹配，不匹配的话直接返回 false 即可，最终判断是否空栈即可，这里我们可以用数组模拟栈的操作使其操作更快，有个细节注意下 top = 1;，从而省去了之后判空的操作和 top - 1 导致数组越界的错误。

思路2

先将左括号对应的右括号押入栈中，枚举字符串中的数据，如果不是左括号，则直接判断元素是否和出栈元素相同。

func isValid(s string) bool {
    stack := make([]rune, len(s))
    top := 0

    for _, c := range s {
        switch (c) {
            case '(' :
                stack[top] = ')'
                top+=1
                break
            case '{' :
                stack[top] = '}'
                top+=1
                break
            case '[' :
                stack[top] = ']'
                top+=1
                break
            default:
                if top == 0 || stack[top-1] != c {
                    return false
                }
                top -=1
                break
        }
    }

    return top == 0
}

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm