LeetCode第20题：有效的括号

0. 序言

"有效的括号"这一题，可以帮助我们更好的理解栈这个数据结构。

1. 题目描述

给定一个只包括'('，')’，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
① 左括号必须用相同类型的右括号闭合。
② 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例1：

输入: "( )"
输出: true

示例2：

输入: "( )[ ]{ }"
输出: true

示例3：

输入: "( ]"
输出: false

示例4：

输入: "( [ ) ]"
输出: false

示例5：

输入: "{ ( ) }"
输出: true

2. 解决方案

• 分析
  ① 字符串元素是偶数个，否则无效，注意0也是偶数。
  ② 括号之间必须是相互对应的关系。
  ③ 除去相互匹配的左右括号之外，不能有任何其他元素。
  ④ 空字符串是一个有效字符串，意味着，空字符串的时候这个字符串有效，即公式返回true。
• 思路
  ① 判断字符串元素的个数是否为偶数，不为偶数个返回false
  ② 创建一个栈，用来存放左括号。
  ③ 判断字符串中的元素是否是右括号，如果是右括号，就看看此时栈顶的左括号是否相互匹配，如果不匹配返回false，如果匹配就把栈顶的元素弹栈，然后再看字符串的下一个元素是否和栈顶的元素相匹配，如果不匹配返回false，循环往复。
  ④ 判断栈是否为空，为空意味着字符串是有效字符串，如果不为空，意味着字符串中的左右括号并非一一对应的关系。
• 代码

import java.util.Stack;

class Solution {
   public boolean isValid(String s) {
        int length = s.length();
        if (length%2!=0)
            return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i <s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            }else{
                if (stack.isEmpty())
                    return false;
                char topChar = stack.pop();
                if (c ==')' && topChar !='('){
                    return false;
                }else if (c =='}' &&topChar !='{'){
                    return false;
                }else if (c ==']' && topChar !='['){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

当然我们也可以把Stack，换为我们自定义的ArrayStack。

3. 复杂度分析

• 时间复杂度分析
  ① 当字符串个数为奇数的时候，时间复杂度为O(1)，这是最好情况时间复杂度。
  ② 当字符串个数为偶数的时候，时间复杂度为O(n)，这是最坏情况时间复杂度。
  ③ 字符串为奇数或偶数的概率，各为1/2,所以1×1/2 + n×1/2 = (n+1)/2，所以加权平均时间复杂度为O(n)
  ④ 这个示例并适合用均摊时间复杂度分析。因为字符串是奇数或者偶数，两者并没有前后关系，对均摊复杂度不了解的，可以跳转阅读：https://www.jianshu.com/p/59f380c6ffcd
  综上：这段代码的时间复杂度为O(n).
• 空间复杂度分析
  涉及多个开括号入栈，所以空间复杂度为O(n)

4. 后续

如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!