我的代码适用于正常的测试用例,例如 ()、()[]{},但在问题中存在一种情况,如果它像 {[]} 一样匹配,则允许返回。所以我解决这个问题的方法,我不知道这是否有效或快速,也是找到括号的位置,然后检查 length() - pos 所以它本质上是向后看,看看它是否匹配第一个括号。下面是我的代码。请让我知道我的工作方向是否正确,以及这是否是一个有效的解决方案。
class Solution {
public:
bool isValid(string s) {
stack<int> s1;
size_t pos = 0;
for(int i = 0; i < s.length(); i++) {
s1.push(s[i]);
if(s1.top() == '(' && s[i+1] != ')') {
pos = s.find(s1.top());
if(s1.top() != s.length() - (pos + 1) ) return false;
}
if(s1.top() == '{' && s[i+1] != '}') {
pos = s.find(s1.top());
if(s1.top() != s.length() - (pos + 1) ) return false;
}
if(s1.top() == '[' && s[i+1] != ']') {
pos = s.find(s1.top());
if(s1.top() != s.length() - (pos + 1) ) return false;
}
}
return true;
}
};
只需使用 stack 来推动左括号并在遇到右括号时检查顶部。 不要尝试同时检查 i 和 i+1 位置。这会修复你的代码。
解决方案:如果使用堆栈推动左括号,然后遇到右括号时检查堆栈顶部。
这是一个有助于解决您的问题的代码示例:
boolean isBalanced(String str) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}