首页 > 代码库 > LeetCode: Valid Parentheses 解题报告
LeetCode: Valid Parentheses 解题报告
Valid Parentheses
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.
SOLUTION1:
使用stack来解决的简单题目。所有的字符依次入栈
1. 遇到成对的括号弹栈，弹栈不成对返回false.
2. 栈为空只能压入左括号
3. 扫描完成时，栈应该为空，否则返回FALSE.
View Code
SOLUTION 2:
使用堆栈解决，比较简单。push右括号时，检查左括号在不在，如果不在，返回false,否则弹出一个左括号。
最后看栈是否为空，不为空代表括号数不对称，也要返回false;
1 public class Solution { 2 public boolean isValid(String s) { 3 if (s == null) { 4 return false; 5 } 6 7 int len = s.length(); 8 9 // bug 1: don‘t use s as the name of the stack.10 Stack<Character> stk = new Stack<Character>();11 12 for (int i = 0; i < len; i++) {13 char c = s.charAt(i);14 switch(c) {15 case ‘(‘:16 case ‘[‘:17 case ‘{‘:18 stk.push(c);19 break;20 case ‘)‘:21 if (!stk.isEmpty() && stk.peek() == ‘(‘) {22 stk.pop();23 } else {24 return false;25 }26 break;27 case ‘}‘:28 if (!stk.isEmpty() && stk.peek() == ‘{‘) {29 stk.pop();30 } else {31 return false;32 }33 break;34 case ‘]‘:35 if (!stk.isEmpty() && stk.peek() == ‘[‘) {36 stk.pop();37 } else {38 return false;39 }40 break; 41 }42 }43 44 return stk.isEmpty();45 }46 }
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/stack/IsValid.java
LeetCode: Valid Parentheses 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。