Press "Enter" to skip to content

Valid Parentheses-LeetCode#20

20. Valid Parentheses

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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. 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
思路:给定一个只包含字符’(’,’)’,'{‘,’}’,'[‘和’]’的字符串,确定输入字符串是否有效。必须使用相同类型的括号关闭左括号。必须以正确的顺序关闭打开括号。
用一个栈,我们开始遍历输入字符串,如果当前字符为左半边括号时,则将其压入栈中,如果遇到右半边括号时,若此时栈为空,则直接返回false,如不为空,则取出栈顶元素,若为对应的左半边括号,则继续循环,反之返回false。
代码如下:
public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> temp = new Stack<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (chars[i] == '(' || chars[i] == '{' || chars[i] == '[') {
                temp.push(chars[i]);
            } else {
                if (temp.empty()) return false;
                if (chars[i] == ')' && temp.peek() != '(') return false;
                if (chars[i] == '}' && temp.peek() != '{') return false;
                if (chars[i] == ']' && temp.peek() != '[') return false;
                temp.pop();
            }
        }
        return temp.empty();
    }
}

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注