今日算法之_30_ 有效的括号
前言
Github:https://github.com/HealerJean
1、有效的括号
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
1.1、解题思路
借助栈存放数据,先进先出,栈里面的存放的数据只能为 ( { [
1.2、算法
1.2.1、解发1、左括号入栈
public boolean isValid(String str) {
Map<Character, Character> map = new HashMap();
map.put('(',')');
map.put('[', ']');
map.put('{', '}');
Stack<Character> stack = new Stack();
for (int i = 0; i < str.length(); i++) {
Character ele = str.charAt(i) ;
//如果属于 map的key值则直接放入栈中
if (map.containsKey(str.charAt(i))){
stack.push(ele);
}else {
//如果不属于 map的key,还能进来肯定有问题
if (stack.isEmpty()){
return false ;
}else if (map.get(stack.peek()).equals(ele)){
stack.pop();
}else {
return false;
}
}
}
if (stack.isEmpty()){
return true;
}
return false ;
}
1.2.2、右括号入栈
/**
* 解法2。和上面原理相同,上面的方法是左括号入栈,下面则是右括号入栈
*/
public boolean isValid2(String s) {
Stack<Character> stack = new Stack();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
//如果不等于栈顶元素则肯定错误,但是如果相等了就出栈
} else if (stack.isEmpty() || c != stack.pop()) {
return false;
}
}
return stack.isEmpty();
}
1.3、测试
@Test
public void test() {
System.out.println(isValid( "()"));
}
true