2015年9月18日星期五

Leetcode 20 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.

Solution 1: Use stack, trick part is to check stack.isEmpty() at the end.
 public class Solution {  
   public boolean isValid(String s) {  
     Deque<Character> stack=new LinkedList<>();  
     int n=s.length();  
     for (int i=0; i<n; i++) {  
       char c=s.charAt(i);  
       if (c=='(' || c=='[' || c=='{') stack.push(c);  
       else if (c==')') {  
         if (stack.isEmpty() || stack.pop()!='(') return false;  
       }  
       else if (c==']') {  
         if (stack.isEmpty() || stack.pop()!='[') return false;  
       }  
       else if (c=='}') {  
         if (stack.isEmpty() || stack.pop()!='{') return false;  
       }  
     }  
     return stack.isEmpty();  
   }  
 }  

没有评论:

发表评论