LeetCode -- Valid Parenthese

Question:

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.

Analysis:

问题描述：给出一个字符串，包含'(', ')', '{', '}', '[' and ']'确定它是否是有效地匹配括号。

思路：一看到括号匹配问题肯定想到用栈。遇到左括号就进栈；遇到右括号若栈顶元素与之匹配则POP出栈顶元素，若不匹配则返回false。

注意特殊情况：如"{}[]()", 或者“{[}]”, 或者“{{}}{{”等情况。

Answer：

public class Solution {

    public boolean isValid(String s) {

        char[] ch = s.toCharArray();

        int n = ch.length;

        if(ch.length == 0 || ch.length % 2 != 0)

            return false;

        if(ch[0] == '}' || ch[0] == ']' || ch[0] == ')')

            return false;

        Stack<Character> st = new Stack<Character>();

        st.add(ch[0]);

        int i = 1;

        while(!st.isEmpty() && i < n) {

            if(ch[i] == '{' || ch[i] == '[' || ch[i] == '(') {

                st.add(ch[i]);

                i++;

            } else {

                if(st.isEmpty())

                    return false;

                char c = st.pop();

                if(c == '{' && ch[i] != '}' || c == '[' && ch[i] != ']'

                        || c == '(' && ch[i] != ')')

                    return false;

                i++;

                if(i < n && (ch[i] == '{' || ch[i] == '[' || ch[i] == '(')) {

                    st.add(ch[i]);

                    i++;

                }

            }

        }

        System.out.println(i +" " +st.size());

        if(!st.isEmpty() || i < n - 1)

            return false;

        return true;

    }

}

巴特西

LeetCode -- Valid Parenthese

最新文章

热门文章