【算法题解】14. 有效的括号

这是一道 简单 题。
来自leetcode

题目

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

有效字符串需满足

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

示例 1

输入s = "()"
输出true

示例 2

输入s = "()[]{}"
输出true

示例 3

输入s = "(]"
输出false

提示
s 仅由括号 ‘()[]{}’ 组成

解法使用栈的特性

有效字符串可以使用 栈的特性先进后出后进先出 来解题。

• 当遇到 左括号‘(’‘[’‘{’时入栈。
• 当遇到 右括号‘)’‘]’‘}’时
  • 若此时栈为空直接返回false。因为前面没有和这个右括号匹配的左括号。
  • 若此时栈顶元素和当前右括号不是一对直接返回false。
  • 若此时栈顶元素和当前右括号成对栈顶元素出栈然后继续遍历字符串中的下一个元素。
• 当将整个字符串遍历完成后
  • 如果此时栈为空返回true。
  • 如果此时栈不空返回false。此时栈中的前括号没有对应的后括号与之成对。

以有效的括号 ‘([]{})’为例动图展示

Java 代码实现

使用 HashMap 存放成对的 前后括号使用时可以直接根据 后括号 获取到与之对应的 前括号。

class Solution {
    public boolean isValid(String s) {

        if(s.length() % 2 != 0){
            return false;
        }

        Map<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put(']', '[');
        pairs.put('}', '{');

        Deque<Character> stack = new LinkedList<>();

        for(char c : s.toCharArray()){
            if(pairs.containsKey(c)){
                if(stack.isEmpty() || stack.peek() != pairs.get(c)){
                    return false;
                }
                stack.pop();
            }else{
                stack.push(c);
            }
        }

        return stack.isEmpty();

    }
}

Go 代码实现

因为Go语言本身没有实现栈这个数据结构所以我们用切片代替思路是一样的。

func isValid(s string) bool {
    n := len(s)
    if n % 2 != 0 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []byte{}
    for i := 0; i < n; i++ {
        if pairs[s[i]] > 0 {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

复杂度分析

时间复杂度$O(N)$N 为字符串长度。
空间复杂度$O(N)$N 为字符串长度。paris 空间复杂度为常数stack 空间复杂度为 N。