文章

LeetCode Valid Parentheses

Problem

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 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package com.coderli.leetcode.algorithms.easy;

/**
 * Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
 * <p>
 * The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
 *
 * @author li.hzh 2017-10-18
 */
public class ValidParentheses {

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

    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        if (s.length() == 0) {
            return true;
        }
        char[] stack = new char[s.length()];
        int lastIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            if (currentChar == '(' || currentChar == '[' || currentChar == '{') {
                stack[lastIndex] = currentChar;
                lastIndex++;
                continue;
            } else {
                if (lastIndex == 0) {
                    return false;
                }
                char lastValue = stack[lastIndex - 1];
                lastIndex--;
                if (currentChar == ')') {
                    if (lastValue != '(') {
                        return false;
                    }
                } else if (currentChar == ']') {
                    if (lastValue != '[') {
                        return false;
                    }
                } else {
                    if (lastValue != '{') {
                        return false;
                    }
                }
            }
        }
        if (lastIndex != 0) {
            return false;
        }
        return true;
    }
}

分析

因为要配对的,首先先pass掉长度是奇数的输入。剩下的输入,如果是左括号,则放入栈中。如果是右括号,从栈里取出最后一个元素进行配对。如果配对则继续。不配对,则说明字符串不合法。

本文由作者按照 CC BY 4.0 进行授权