首页 > 代码库 > 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.

 

 1 public class Solution { 2     public boolean isValid(String s) { 3         if (s == null || s.length() == 0) { 4             return true; 5         } 6          7         Stack<Character> stack = new Stack<Character>(); 8         int len = s.length(); 9         for (int i = 0; i < len; i++) {10             char c = s.charAt(i);11             if (stack.isEmpty()) {12                 // 栈为空的时候,不能放右括号13                 if (c == ‘]‘ || c == ‘)‘ || c == ‘}‘) {14                     return false;15                 }16                 stack.push(c);17                 continue;18             }19             20             // 栈不为空时,必须 要对应弹出相对应的括号21             if (c == ‘)‘ && stack.peek() == ‘(‘22                || c == ‘]‘ && stack.peek() == ‘[‘23                || c == ‘}‘ && stack.peek() == ‘{‘24                ) {25                 stack.pop();26             // 或者继续压入左括号    27             } else if (c == ‘(‘ || c == ‘[‘ || c == ‘{‘) {28                 stack.push(c);29             // 否则错误退出    30             } else {31                 return false;32             }33         }34         35         return stack.isEmpty();36     }37 }
View Code

 

 

GITHUB CODE

 

LeetCode: Valid Parentheses 解题报告