[数据结构与算法]【LeetCode - Java】20. 有效的括号 （简单）

1. 题目描述

2. 解题思路

这道题目比较简单，经典的解题思路就是利用栈，从字符串中依次取出字符与栈顶进行匹配，不能匹配的符号进栈，能够匹配的符号出栈，最后若栈为空则表明字符串中所有的括号都能够完全匹配。

问题来了，怎么样判断两个字符是否为匹配关系呢？看了一眼ASCII表，发现(与)的ASCII码相差1，[与]和{与}的ASCII码都是相差2，于是乎这个就成为了我的判断依据。其他解答中也有利用HashMap实现的，但我个人还是认为利用ASCII更方便。

在Java实现中尝试了三种解决方案，分别是栈、数组和链表，但主体思想还是栈先进后出的特性。

3. 代码实现

3.1 栈（Stack）

	public boolean isValid(String s) {
        Stack<Character> chars = new Stack<Character>();
        if (s.length() % 2 == 0) {
            for (int i = 0; i < s.length(); i++) {
                if (!chars.empty()) {
                    if (s.charAt(i) - chars.peek() == 2 || s.charAt(i) - chars.peek() == 1)
                        chars.pop();
                    else
                        chars.push(s.charAt(i));
                } else
                    chars.push(s.charAt(i));
            }
            return chars.empty();
        } else
            return false;
    }

3.2 数组（ArrayList）

public boolean isValid(String s) {
        List<Character> characters = new ArrayList<>();
        int l = s.length();
        if (l % 2 == 0) {
            for (int i = 0; i < l; i++) {
                if (!characters.isEmpty()) {
                    if (s.charAt(i) - characters.get(characters.size() - 1) == 1 || s.charAt(i) - characters.get(characters.size() - 1) == 2)
                        characters.remove(characters.size() - 1);
                    else
                        characters.add(s.charAt(i));
                } else
                    characters.add(s.charAt(i));
            }
            return characters.isEmpty();
        } else
            return false;
    }

3.3 链表（LinkedList）

public boolean isValid(String s) {
        LinkedList<Character> chars = new LinkedList<>();
        if (s.length() % 2 == 0) {
            for (int i = 0; i < s.length(); i++) {
                if (!chars.isEmpty()) {
                    if (s.charAt(i) - chars.getLast() == 2 || s.charAt(i) - chars.getLast() == 1)
                        chars.removeLast();
                    else
                        chars.addLast(s.charAt(i));
                } else
                    chars.addLast(s.charAt(i));
            }
            return chars.isEmpty();
        } else
            return false;
    }

3.4 对比

显然，三种方案之间几乎没有优劣之分，性能表现也几乎一致，时间复杂度都为O(n)，n为字符串的长度。过后看了一下官解也是这种思路，但暂时还没发现效率更高占用空间更少的算法。