20. Valid Parentheses

[yunshuipiao]

20. Valid Parentheses

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
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

解法

简单题目，借助栈来保存即可。要注意有亮点：

1. 当前字符必须和栈顶字符匹配
2. 假设字符为 "( { [ [ } )", 栈中保存的为 "[ [ "。因此最后需要判断栈是否为空。

fun isValid(s: String): Boolean {
    val map = hashMapOf('(' to ')', '{' to '}', '[' to ']')
    val result = ArrayList<Char>()
    for (c in s) {
        println(c)
        if (c in map.keys) {
            result.add(c)
        } else {
            if (result.isEmpty() || map[result.last()] != c) {
                return false
            } else {
                result.removeAt(result.size - 1)
            }
        }
    }
    return result.isEmpty()
}