LeetCode #20 – Valid Parentheses [Stack]

链接:https://leetcode.com/problems/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.

题意:给定一个字符序列,判断是否是合法的括号序列,即符合一一配对。

分析:简单的数据结构栈的题。

代码:(Java好慢啊…)
Java:

public class Solution {
    public boolean match(Character a, Character b) {
        return (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}');
    }
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<Character>();
        for(int i = 0; i != s.length(); ++i) {
            Character cur = s.charAt(i);
            if(st.empty() || !match(st.peek(), cur))
                st.push(cur);
            else st.pop();
        }
        return st.empty();
    }
}

Python:

class Solution:
    def match(self, a, b):
        return (a=='[' and b==']') or (a=='(' and b==')') or (a=='{' and b=='}')
    def isValid(self, s):
        st = []
        for i in s:
            if len(st) == 0 or (not self.match(st[-1], i)):
               st.append(i)
            else: st.pop()
        return len(st) == 0

欢迎留言