给出一个仅包含字符'(',')','{','}','['和']',的字符串,判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭,"()"和"()[]{}"都是合法的括号序列,但"(]"和"([)]"不合法。
括号必须以正确的顺序关闭,"()"和"()[]{}"都是合法的括号序列,但"(]"和"([)]"不合法。
数据范围:字符串长度
要求:空间复杂度 ,时间复杂度
bool isValid(string s) { // write code here if (s.size() <= 1) { return false; } stack<char> temp; for(int i = 0; i<s.size();i++) { if(temp.size() == 0) { temp.push(s[i]); } else { char ch = temp.top(); if((ch == '(' && s[i] == ')') || (ch == '[' && s[i] == ']') || (ch == '{' && s[i] == '}')) { temp.pop(); } else { temp.push(s[i]); } } } return temp.size() == 0 ? 1 :0; } };
import java.util.Stack; public class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<Character>(); //使用foreach循环 for (char c : s.toCharArray()) { if (c == '(') stack.push(')'); else if (c == '{') stack.push('}'); else if (c == '[') stack.push(']'); else if (stack.isEmpty() || stack.pop() != c) return false; } return stack.isEmpty(); } }
class Solution {
public:
bool isValid(string s) {
int len=s.size();
stack<char> sta;
for(int i=0;i<len;i++){
if(s[i]=='(')sta.push(')');
else if(s[i]=='[')sta.push(']');
else if(s[i]=='{')sta.push('}');
else if(sta.empty())return false;
else if(sta.top()!=s[i])return false;
else sta.pop();
}
return sta.empty();
}
};
class Solution { public: bool isValid(string s) { int l = s.length(); stack<char> st; for(int i=0;i<l;i++) { if(s[i] == '(') st.push(')'); else if(s[i] == '[') st.push(']'); else if(s[i] == '{') st.push('}'); else if(st.empty()) return false; else if(st.top() != s[i]) return false; else st.pop(); } return st.empty(); } };
import java.util.Stack;
/**
* 20. Valid ParentTheses
* 有效的括号
* <p>
* 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
* 有效字符串需满足:
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
* 注意空字符串可被认为是有效字符串。
* 示例 1:
* 输入: "()"
* 输出: true
* 示例 2:
* 输入: "()[]{}"
* 输出: true
* 示例 3:
* 输入: "(]"
* 输出: false
* 示例 4:
* 输入: "([)]"
* 输出: false
* 示例 5:
* 输入: "{[]}"
* 输出: true
*/
public class Solution {
/**
* 用压栈弹栈的方式来实现
*/
public boolean isValid(String s) {
if (s == null || s.length() == 0){
return true;
}
Stack<Character> stack = new Stack<>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '('){
stack.push(')');
}
else if (chars[i] == '['){
stack.push(']');
}
else if (chars[i] == '{'){
stack.push('}');
}
else if (stack.isEmpty() || chars[i] != stack.pop()){
return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args){
Solution solution = new Solution();
System.out.println(solution.isValid(""));
System.out.println(solution.isValid("()[]{}"));
System.out.println(solution.isValid("(]"));
System.out.println(solution.isValid("([)]"));
System.out.println(solution.isValid("{[]}"));
}
}
class Solution { public: bool isValid(string s) { stack<char>st; for(int i=0;i<s.size();i++) { if(s[i]=='('||s[i]=='['||s[i]=='{') st.push(s[i]); else { if(st.empty()) return false; else { if(s[i]==')'&&st.top()=='(') st.pop(); else if(s[i]==']'&&st.top()=='[') st.pop(); else if(s[i]=='}'&&st.top()=='{') st.pop(); } } } if(st.empty()) return true; else return false; } };
class Solution(object): def isValid(self, s): stack = [] for ss in s: if ss == "(" or ss == "{" or ss == "[": stack.append(ss) elif ss == ")": if len(stack) == 0 or stack.pop() != "(": return False elif ss == "}": if len(stack) == 0 or stack.pop() != "{": return False elif ss == "]": if len(stack) == 0 or stack.pop() != "[": return False return len(stack) == 0
public boolean isValid (String s) { // write code here //遇到括号匹配这样的题,首选使用栈来做 //每次遍历遇到'('、'['和'{'时,就将其对应的方括号')'、']'和'}'放入栈中 //然后遍历下一个,并与栈顶元素进行比较 //如果不同直接返回false;如果相同就将栈顶的反括号弹出,遍历结束都没有返回false就说明合法,返回true Stack<Character> stack = new Stack<>(); char[] temp = s.toCharArray(); for (char c : temp){//遍历字符,如果遇到左括号,就把相应的右括号压入栈顶 if (c == '(') stack.push(')'); else if (c == '[') stack.push(']'); else if (c == '{') stack.push('}'); //else if (stack.isEmpty()) return false;//字符还没有遍历完就出现栈为空就返回false //else if (stack.pop() != c) return false;//如果能到达这一步,就每次从栈顶pop出一个元素与当前元素c //进行比较,如果不同就返回false //也可以将上面两行代码合并: else if (stack.isEmpty() || stack.pop() != c) return false; } return stack.isEmpty();//遍历结束如果栈为空就返回true,否则返回false }
class Solution { unordered_map<char, char> map = {{'{', '}'}, {'[', ']'}, {'(', ')'}}; public: /** * * @param s string字符串 * @return bool布尔型 */ bool isValid(string s) { stack<char> st; for (char& ch : s) { if (st.empty() || map[st.top()] != ch) { st.push(ch); } else { st.pop(); } } return st.empty(); } };
import java.util.*; public class Solution { /** * * @param s string字符串 * @return bool布尔型 */ public boolean isValid (String s) { // write code here // write code here int length = s.length(); if (length % 2 != 0) { return false; } String s1 = s; for (int i = 0; i < length / 2; i++) { s1 = s1.replace("()", "").replace("[]", "").replace("{}", ""); } return s1.length() <= 0; } }我偷鸡了😂
int i = 0, j = -1; char a[10000]; bool isValid(char* s ) { // write code here while (s[i] != '\0') { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { //左括号进栈 a[++j] = s[i]; } else { //是右括号则判断是否匹配 if (s[i] == ')' && a[j] != '(') return false; else if (s[i] == ']' && a[j] != '[') return false; else if (s[i] == '}' && a[j] != '{') return false; else j--; } i++; //指向字符串下一个字符 } if (j >= 0) return false; //栈非空 else return true; }
public boolean isValid (String s) { // write code here Stack<Character> stack = new Stack<>(); for(int i=0;i<s.length();i++){ char c = s.charAt(i); if(c=='['){ stack.push(']'); }else if(c=='{'){ stack.push('}'); }else if(c=='('){ stack.push(')'); }else if(stack.isEmpty() || stack.pop()!=c){ return false; } } return stack.isEmpty(); }
class Solution {
public:
bool isValid(string s) {
stack<char>S;
for(int i=0;i<s.length();++i){
if(s[i]=='[' || s[i]=='(' || s[i]=='{') S.push(s[i]);
else if(S.empty()) return false;
else if(s[i]==']' && S.top()=='[' || s[i]=='}' && S.top()=='{' || s[i]==')' && S.top()=='(') S.pop();
else return false;
}
if(S.empty()) return true;
else return false;
}
};
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ public boolean isValid (String s) { // write code here Map<Character, Character> map = new HashMap<>(); map.put(')', '('); map.put(']', '['); map.put('}', '{'); Stack<Character> signs = new Stack<>(); for (int i = 0; i < s.length(); i++) { if (signs.empty() || map.values().contains(s.charAt(i))) { // open sign signs.push(s.charAt(i)); } else { // close sign if (signs.peek() == map.get(s.charAt(i))) { signs.pop(); } } } return signs.empty() ? true : false; } }
public boolean isValid (String s) { Stack<Character> st=new Stack<>(); for(int i=0;i<s.length();i++){ if(s.charAt(i)=='('){ st.push(')'); }else if(s.charAt(i)=='['){ st.push(']'); }else if(s.charAt(i)=='{'){ st.push('}'); }else{ //不是增加元素,是要弹出,但st为空,那就false if(st.isEmpty()){ return false; } if(st.pop()!=s.charAt(i)){ return false; } } } if(!st.isEmpty()){ return false; } return true; }
public boolean isValid (String s) { // write code here //利用哈希存储字符,避免if语句中出现冗余比较语句 HashMap<Character, Character> map = new HashMap<Character, Character>() { { put(')', '('); put(']', '['); put('}', '{'); } }; Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (map.containsKey(c)) { if (stack.isEmpty()) return false; if (map.get(c) != stack.peek()) return false; stack.pop(); } else { stack.push(c); } } return stack.isEmpty(); }