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;
};

參考資料