当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.020.Valid Parentheses

LeetCode.020.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.


解题过程

括号匹配,一看就知道是用栈,遇到左括号入栈,遇到右括号出栈匹配,不过还是有需要注意的地方,比方说匹配过程中如果栈为空则错误(右括号多),匹配完成后栈不空也是错误的(左括号多)。

package _020_ValidParentheses;

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<String> stack = new Stack<String>();
        for(int i=0; i<s.length(); i++){
            char ch = s.charAt(i);
            if(ch=='(' || ch=='[' || ch=='{'){
                switch (ch) {
                case '(': stack.push(")"); break;    
                case '[': stack.push("]"); break;
                case '{': stack.push("}"); break;
                default: break;
                }
            }else{
                if(stack.isEmpty()){//中途栈为空说明不匹配
                    return false;
                }else if(!stack.pop().equals(s.substring(i, i+1))){
                    return false;
                }    
            }
        }
        return stack.isEmpty() ? true : false;//最后栈为空才匹配
    }
}

public class ValidParentheses {
    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.isValid("[(){}]]"));
    }
}

我的代码速度不快,我看速度快的基本上都是用数组模拟栈,而不是直接用Java中的Stack。


GitHub代码


上一篇 Hexo博客(21)创建博客概览插件

下一篇 LeetCode.021.Merge Two Sorted Lists

阅读
288
阅读预计1分钟
创建日期 2018-02-10
修改日期 2018-02-12
类别
百度推荐