导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一:利用栈匹配
    2. 方法二:每次去除字符串中已经相邻匹配的括号,循环判断:

LeetCode-20.Valid Parentheses

题目

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

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

翻译

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

方法一:利用栈匹配

当栈为空时,压栈;当栈不为空时,取出顶部元素,如果与当前字符匹配为一对括号,则出栈,否则压栈。不断循环,最后如果栈为空则合法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char curChar : s.toCharArray()) {
if (stack.isEmpty()) {
stack.push(curChar);
continue;
}
char lastChar = stack.peek();
if (lastChar == '(' && curChar == ')') stack.pop();
else if (lastChar == '[' && curChar == ']') stack.pop();
else if (lastChar == '{' && curChar == '}') stack.pop();
else stack.push(curChar);
}
return stack.isEmpty();
}

方法二:每次去除字符串中已经相邻匹配的括号,循环判断:

1
2
3
4
5
public boolean isValid(String s) {
while (s.contains("()") || s.contains("[]") || s.contains("{}"))
s = s.replace("()", "").replace("[]", "").replace("{}", "");
return s.length() == 0;
}

效率低一些,但是思路很新颖。

参考:
http://www.2cto.com/kf/201411/355360.html