力扣算法 - 有效的括号

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

思路:

    /***
     * 思路:
     * 遇见左字符,就入栈, 遇到右字符
     * 如果栈为空, 即没有相应的左字符与之对应, 就说明括号无效
     * 如果栈不为空, 将栈顶字符出栈与之匹配
     * 如果匹配成功, 继续扫描下一个字符
     * 如果匹配不成功, 说明括号无效
     * 直到所有字符扫描完毕
     * 栈不为空, 括号有效
     * 栈为空, 括号无效
     */

Java实现

   public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');

        char[] sArray = s.toCharArray();

        Stack<Character> stack = new Stack<>();

        for (char character : sArray) {
            // 左字符
            if (map.containsKey(character)) {
                stack.push(character);
            } else {  // 右字符
                if (stack.isEmpty()) return false;
                if ( character != map.get(stack.pop())) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

Swift实现

    func isValid(_ s: String) -> Bool {
        
        var map:[Character: Character] = Dictionary()
        map["("] = ")"
        map["{"] = "}"
        map["["] = "]"
        
        var stask = [Character]()
        for char in s {
            //左字符
            if map.keys.contains(char) {
                stask.append(char)
            } else { // 右字符
                if stask.isEmpty {
                    return false
                }
                
                if char != map[stask.popLast()!] {
                    return false
                }
            }
        }
        return stask.isEmpty
    }