（Java）leetcode-20 Valid Parentheses

桃扇骨 2022-02-28 01:06 129阅读 0赞

# 题目 #

【括弧匹配】

Given a string containing just the characters ‘(’, ‘)’, ‘\{’, ‘\}’, ‘\[’ and ‘\]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.  
Open brackets must be closed in the correct order.  
Note that an empty string is also considered valid.

Example 1:

Input: “()”  
Output: true  
Example 2:

Input: “()\[\]\{\}”  
Output: true  
Example 3:

Input: “(\]”  
Output: false  
Example 4:

Input: “(\[)\]”  
Output: false  
Example 5:

Input: “\{\[\]\}”  
Output: true

# 思路1 #

使用堆栈，遍历字符串，取当前元素与栈顶元素比较，若配对，则出栈，否则入栈，最后判断栈若为空说明字符串是括弧匹配的，反之不是

## 代码1 ##

class Solution { 
        public boolean isValid(String s) { 
            if (s.length()==0) return true;
            Stack<Character> stack = new Stack<Character>();
            int i = 1;
            stack.push(s.charAt(0));
            
            while( i<s.length()){ 
                
            	if(s.charAt(i) == ')' && stack.peek() == '('){ 
            		stack.pop();        		
            	}
    
            	else if(s.charAt(i) == ']' && stack.peek() == '['){ 
            		stack.pop();
            		
            	}
    
            	else if(s.charAt(i) == '}' && stack.peek() == '{'){ 
            		stack.pop();
            		
            	}
                else stack.push(s.charAt(i));//若与栈顶不匹配则当前元素入栈
                //当栈空且字符串还未遍历完，则将后一个元素入栈，否则stack.peek(）会报错
                if (stack.empty() && i<s.length()-1) { 
                	stack.push(s.charAt(i+1)); i+=1;
                }
            	i++;
                
            }
            //遍历完之后的判定
            return stack.isEmpty();
    
        }
    }

## 提交结果 ##

Runtime: 4 ms, faster than 89.44% of Java online submissions for Valid Parentheses.  
Memory Usage: 36.9 MB, less than 35.30% of Java online submissions for Valid Parentheses.

# 思路2-改进 #

*  其实没有必要非要把整个字符串遍历完再判断，可以在遍历的过程中一旦发现不匹配，立即 return false 。
 *  此外，’(’ ‘\{’ ‘\[’ 这三个左括号可以无需判断栈顶直接入栈，并且，入栈时直接入栈对应的右括号，那么遍历至下一个元素时（若该元素为右括号），直接出栈并判定出栈元素与当前字符是否相等即可

## 代码2 ##

class Solution{ 
    	public boolean isValid(String s) { 
    		Stack<Character> stack = new Stack<Character>();
    		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();
    	}
    }

## 提交结果 ##

Runtime: 3 ms, faster than 99.61% of Java online submissions for Valid Parentheses.  
Memory Usage: 36.7 MB, less than 36.06% of Java online submissions for Valid Parentheses.