20. Valid Parentheses

Leetcode 问题: 20. Valid Parentheses
Categories:
Tags:

题目

Given a string s 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.

传入符号字串 s，判断字串是否为合法的符号字串

  • 开启的括弧，必须有一个结束的同类型括弧
  • 开启的括弧，必须用正确的顺序结束括弧关闭

Example

Input: s = "()"
Output: true

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

演算法

1. 产生符号顺序纪录的 Stack

因为符号的先后顺序有差别的，所以先检查到的符号要最后才能够拿出来，需要用 Stack 的方式，让符号资料后进先出(LIFO)

2. 产生结束括弧（closing parentheses）对应的起始括弧（open parentheses）对应 Map

当检查到的结束括弧（closing parentheses）时，要确认在 Stack 要取的哪个 起始括弧（open parentheses）

所以必须有括弧对应 Map 去对应

当有对应到 Stack 中正确的起始括弧，再将 Stack 资料 pop 取出

如果没有对应到 Stack 中正确的起始括弧，表示这个括弧字串是不合法的，回传 false

3. 如果不是结束括号，将符号加入 Stack

检查的符号如果不是结束符号，依序地将符号加入到 Stack，然后从最后面依序检查

答案

JavaScript

function isValid(checkParenthesesString) {
    // 括号 Stack
    var parenthesesStack = [];
    // 结束括号对应开始括号
    var closeToOpenParenthesesMap = new Map();
    closeToOpenParenthesesMap.set(")", "(");
    closeToOpenParenthesesMap.set("]", "[");
    closeToOpenParenthesesMap.set("}", "{");
    for (var i = 0; i < checkParenthesesString.length; i++) {
        // 从头开始检查括号
        // 目前括号
        var currentParentheses = checkParenthesesString[i];
        if (closeToOpenParenthesesMap.has(currentParentheses)) {
            // 如果是结束的括号
            // 目前括号 Stack 数量
            var currentStackElementCount = parenthesesStack.length;
            // 目前符号的起始括号
            var currentOpenParentheses = closeToOpenParenthesesMap.get(currentParentheses);
            if (currentStackElementCount > 0 && parenthesesStack[currentStackElementCount - 1] == currentOpenParentheses) {
                // 如果目前 Stack 有括号元素
                // 且「Stack 最后一个元素」与「目前括号对应的起始元素」相同
                // 表示括号前后有对应，将此括号从 Stack 中移出
                parenthesesStack.pop();
            }
            else {
                // 如果 Stack 中没有任何的元素，表示无法对应到任何起始括号了
                // 或者「Stack 最后一个元素」与「目前括号对应的起始元素」不相同
                // 表示括号前后无对应
                return false;
            }
        }
        else {
            // 如果是开始的括号，加入 Stack
            parenthesesStack.push(currentParentheses);
        }
    }
    // 预设不是合法的括弧
    var isValidParentheses = false;
    if (parenthesesStack.length == 0) {
        // 如果 Stack 都没有对应的括弧资料了，表示所有的括弧都正确的对应完毕，是合法的括弧
        isValidParentheses = true;
    }
    return isValidParentheses;
}

TypeScript

function isValid(checkParenthesesString: string): boolean {
    // 括号 Stack
    let parenthesesStack = [];
    // 结束括号对应开始括号
    let closeToOpenParenthesesMap = new Map();
    closeToOpenParenthesesMap.set(")", "(");
    closeToOpenParenthesesMap.set("]", "[");
    closeToOpenParenthesesMap.set("}", "{");


    for (let i = 0; i < checkParenthesesString.length; i++) {
        // 从头开始检查括号
        // 目前括号
        let currentParentheses = checkParenthesesString[i];

        if (closeToOpenParenthesesMap.has(currentParentheses)) {
            // 如果是结束的括号
            // 目前括号 Stack 数量
            let currentStackElementCount = parenthesesStack.length;
            // 目前符号的起始括号
            let currentOpenParentheses = closeToOpenParenthesesMap.get(currentParentheses);
            if (currentStackElementCount > 0 && parenthesesStack[currentStackElementCount - 1] == currentOpenParentheses) {
                // 如果目前 Stack 有括号元素
                // 且「Stack 最后一个元素」与「目前括号对应的起始元素」相同
                // 表示括号前后有对应，将此括号从 Stack 中移出
                parenthesesStack.pop();
            } else {
                // 如果 Stack 中没有任何的元素，表示无法对应到任何起始括号了
                // 或者「Stack 最后一个元素」与「目前括号对应的起始元素」不相同
                // 表示括号前后无对应
                return false;
            }
        } else {
            // 如果是开始的括号，加入 Stack
            parenthesesStack.push(currentParentheses);
        }
    }

    // 预设不是合法的括弧
    let isValidParentheses = false;
    if (parenthesesStack.length ==0) {
        // 如果 Stack 都没有对应的括弧资料了，表示所有的括弧都正确的对应完毕，是合法的括弧
        isValidParentheses = true;
    }

    return isValidParentheses;
};

参考资料