算法系列——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.

解题思路

括号匹配,典型栈的应用。利用栈结构,遍历字符串,遇到 左括号入栈,当遇到右括号时,查看栈顶是否是对应的左括号,如果是出栈。否则直接返回false。遍历完成后,查看栈中是否为空,如果不为空返回false,否则返回true.

程序分析

public class Solution {
    public boolean isValid(String s) {
        Stack st=new Stack();
        if(s.length()==0||s.length()%2!=0)
            return false;
        int i = 0;
        while (i < s.length()) {
            switch (s.charAt(i)) {
            case '(':
            case '{':
            case '[':
                st.push(s.charAt(i));
                break;
            case ']':
            case '}':
            case ')':
                if(st.isEmpty())
                    return false;
                if(map(s.charAt(i))!=st.peek())
                    return false;
                else
                    st.pop();
                break;
            default:
                return false;//其他字符,直接返回false
            }
            i++;
        }
        if(!st.isEmpty())//如果栈不为空
            return false;
        return true;
    }

    public char map(char ch) {
        char result = ' ';
        switch (ch) {
        case '}':
            result = '{';
            break;
        case ']':
            result = '[';
            break;
        case ')':
            result = '(';
            break;

        default:
            break;
        }
        return result;

    }
}
CSDN博客责编内容来自:CSDN博客 (源链) | 更多关于

阅读提示:酷辣虫无法对本内容的真实性提供任何保证,请自行验证并承担相关的风险与后果!
本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » 算法系列——Valid Parentheses

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录