Valid Parentheses

首發地址：http://www.brandhuang.com/article/1583660931568

有效的括號:

說明：現階段的解題暫未考慮複雜度問題

Question：

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:

<code>
Input: "()"
Output: true
Input: "()[]{}"
Output: true
Input: "(]"
Output: false
Input: "([)]"
Output: false 

Input: "{[]}"
Output: true
/<code>

個人分析：

1. 由題目「空字符串可被認為是有效字符串」, 當輸入空字符串時，返回 true。
2. 聲明一個對象(Obj)，用對象的 key 和 value 值來保存這成對出現的括號，要滿足題目中「有效的字符串」,必定是以左括號開始，右括號閉合，所以我們用 Obj 的 key 來存左括號，key 對應的 value 值來存右括號。
3. 遍歷輸入的字符串，聲明一個數組(arr)，來存放遍歷出的和 Obj 中的 key 相等的字符。
4. 如果遍歷出的元素不是 Obj 中的 key，說明此元素必定是一個右括號。
5. 取出第 3 步中存入數組中的字符，如果從數組中取出的值在Obj 中對應的 value 和第 4 步遍歷出的元素相同，則說明是一個有效的字符，否則這個 右括號 沒有對應的 左括號，是一個無效的字符串， 此時返回false。
6. 如果在遍歷完輸入的字符串後，第 3 步中的數組為空，則說明輸入的字符串剛好都是 有效的字符串，否則是 無效字符串。
7. 得出如下答案。

Answer：

<code>var isValid = function (s) {
    if (!s) return true
    let obj = {
        '(': ')',
        '{': '}',
        '[': ']',
    }
    let arr = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] in obj) {
            arr.push(s[i])
        } else {
            var current = arr.pop()
            if (obj[current] !== s[i]) {
                return false
            }
        }
    }
    return arr.length === 0
};
/<code>

其他：

本題更多 JavaScript 解析，點擊「瞭解更多」，文章底部查看更多答案。

閱讀更多 重慶崽兒Brand 的文章

關鍵字: 複雜度 暫未 JavaScript