题目描述

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

题目分析

使用栈进行模拟，遇到左括号入栈，遇到右括号则出栈进行匹配

Java

public boolean isValid(String s) {
    Deque<Character> stack = new LinkedList<>();
    HashMap<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('{', '}');
    map.put('[', ']');
    for (int i = 0; i < s.length(); i++) {
        Character ch = s.charAt(i);
        if (map.containsKey(ch)) {
            stack.push(ch);
        } else if (stack.isEmpty() || !ch.equals(map.get(stack.pop()))) {
            return false;
        }
    }
    return stack.isEmpty();
}

Kotlin

fun isValid(s: String): Boolean {
    val stack = LinkedList<Char>()
    val map = mapOf(
        Pair('(', ')'),
        Pair('[', ']'),
        Pair('{', '}'),
    )
    for (ch in s) {
        if (ch in map.keys) {
            stack.push(ch)
        } else if (stack.isEmpty() || ch != map[stack.pop()]) {
            return false
        }
    }
    return stack.isEmpty()
}