LeetCode算法题之有效的括号
有效的括号
题目：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
解题思路，采用最简单粗暴的写法，判断左右括号数量， 并且使用 集合存储左括号出现的位置，匹配的右括号出现remove掉，来判断括号的顺序
上代码：（这种解法没有使用map， 栈数据结构，后续会更新其他写法） Java
解法一：
class Solution {
public boolean isValid(String s) {
int leftSmall = 0;
int rightSmall = 0;
int leftMiddle = 0;
int rightMiddle = 0;
int leftBig = 0;
int rightBig = 0;
// 记录上一次左括号的位置，用来判断顺序
List<Integer> lastSmall = new ArrayList();
List<Integer> lastMiddle = new ArrayList();
List<Integer> lastBig = new ArrayList();
lastSmall.add(-1);
lastMiddle.add(-1);
lastBig.add(-1);
for (int i = 0; i < s.length(); i++) {
String c = String.valueOf(s.charAt(i));
if ("(".equals(c)) {
leftSmall++;
lastSmall.add(i);
}
else if (")".equals(c)) {
rightSmall++;
if (lastSmall.size() == 1 || lastBig.get(lastBig.size() - 1) > lastSmall.get(lastSmall.size() - 1) || lastMiddle.get(lastMiddle.size() - 1) > lastSmall.get(lastSmall.size() - 1)) {
return false;
}
lastSmall.remove(lastSmall.size() - 1); //表示左右顺序正确抵消
}
else if ("[".equals(c)) {
leftMiddle++;
lastMiddle.add(i);
}
else if ("]".equals(c)) {
rightMiddle++;
if (lastMiddle.size() == 1 || lastBig.get(lastBig.size() - 1) > lastMiddle.get(lastMiddle.size() - 1) || lastSmall.get(lastSmall.size() - 1) > lastMiddle.get(lastMiddle.size() - 1)) {
return false;
}
lastMiddle.remove(lastMiddle.size() - 1);
}
else if ("{".equals(c)) {
leftBig++;
lastBig.add(i);
}
else if ("}".equals(c)) {
rightBig++;
if (lastBig.size() == 1 || lastSmall.get(lastSmall.size() - 1) > lastBig.get(lastBig.size() - 1) || lastMiddle.get(lastMiddle.size() - 1) > lastBig.get(lastBig.size() - 1)) {
return false;
}
lastBig.remove(lastBig.size() - 1);
}
else {
continue;
}
}
if (leftBig != rightBig || leftMiddle != rightMiddle || leftSmall != rightSmall) {
return false;
}
return true;
}
}