描述
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.
分析
这道题目,,,我见过的,,,
这类题目基本上就是用栈的思路吧,首先入栈的当然不能是')'
,'}'
,']'
,之后凡是入栈的括号,如果是左括号直接入栈,不是左括号,判断是否与栈顶匹配,不匹配就是false,匹配就消除这一对,最后要做一下判断,如果最后的栈中还有元素(左括号),那么也不是valid。
解决方案1(Python)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution: def isValid(self, s: str) -> bool: if len(s) % 2 == 1: return False pairs = { ")": "(", "]": "[", "}": "{", } stack = list() for ch in s: if ch in pairs: if not stack or stack[-1] != pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack
|
解决方案2(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| class Solution { public: bool isValid(string s) { stack<char> charStack; for(int i = 0; i < s.length(); i++) { char nowChar = s[i]; if(nowChar != ')' && nowChar != ']' && nowChar != '}') { charStack.push(nowChar); }else { if(charStack.size() == 0) { return false; } char preChar = charStack.top(); switch(nowChar) { case ')': if(preChar == '(') { charStack.pop(); }else { return false; } break; case ']': if(preChar == '[') { charStack.pop(); }else { return false; } break; case '}': if(preChar == '{') { charStack.pop(); }else { return false; } break; } } } if(charStack.size() == 0) { return true; }else { return false; } } };
|
解决方案3(Rust)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| impl Solution { pub fn is_valid(s: String) -> bool { let mut stack: Vec<char> = Vec::new(); for ch in s.chars().into_iter() { match stack.last() { None => {} Some(&last) => { if Solution::pair(last, ch) { stack.pop(); continue } } } stack.push(ch); } stack.is_empty() } #[inline(always)] fn pair(left: char, close: char) -> bool { (left == '{' && close == '}') || (left == '(' && close == ')') || (left == '[' && close == ']') } }
|
解决方案4(Golang)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| func isValid(s string) bool { if s == "" { return true } var stack []uint8 parenthesesMap := map[uint8]uint8 { '}': '{', ')': '(', ']': '[', } for i := 0; i < len(s); i++ { if s[i] == '{' || s[i] == '[' || s[i] == '(' { stack = append(stack, s[i]) } else { if len(stack) == 0 { return false } if parenthesesMap[s[i]] != stack[len(stack)-1] { return false } stack = stack[:len(stack)-1] } } return len(stack) == 0 }
|
相关问题