LeetCode-有效的括号

发表于 | 分类于 | 阅读次数:

题目

出处：LeetCode 算法第20题

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

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

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

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

示例 5:

1
2
输入: "{[]}"
输出: true

思路

  • 大家应该都还记得数据结构中有一个栈的概念，我们可以利用栈的先进后出的特性来做这道题
  • 先将他们转换为char类型的字符串，将其一个一个字符的进行判断，如果它是这三种类型中任意一个的左括号则将他们压栈；如果它是右括号，则查看栈顶是否是与之相对应的左括号，若是则将该左括号弹栈，继续下一个字符的操作；若不是，则该字符串不是一个有效的字符串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean isValid(String s) {
		
		Stack<Character> stack = new Stack();		
		
		for (int i = 0; i < s.length(); i++){
			char ch = s.charAt(i);
			if(ch == '(' || ch == '[' || ch == '{' ){
                stack.push(ch);
            } else{
				if (stack.isEmpty()){
					return false;
				}
				
				char topChar = stack.pop();
				if(ch == ')' && topChar != '(' ){
                    return false;
                }else if(ch == ']' && topChar != '[' ){
                    return false;
                }else if(ch == '}' && topChar != '{' ){
                    return false;
                }

			}
		}
        return stack.isEmpty();
    }
}