LeetCode 20：有效的括號 Valid Parentheses

TesterHome 發布于2019-08-19 10:17 / 2630人閱讀

摘要：給定一個只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號必須用相同類型的右括號閉合。注意空字符串可被認為是有效字符串。

給定一個只包括 "("，")"，"{"，"}"，"["，"]" 的字符串，判斷字符串是否有效。

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.

示例 1:

輸入: "()"
輸出: true

示例 2:

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

示例 3:

輸入: "(]"
輸出: false

示例 4:

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

示例 5:

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

解題思路：

很簡單的題，將字符串每個字符壓入棧，簡單判斷即可。如：

輸入: "{[]}"
初始棧為空，"{" 入棧
下一個字符
棧頂元素 "{"與 "[" 不匹配，"[" 入棧
下一個字符
棧頂元素 "["與 "]" 匹配，"[" 出棧
下一個字符
棧頂元素 "{"與 "}" 匹配，"}" 出棧
結束，棧為空，返回 True

關鍵在于判斷字符是否匹配，匹配的標準是相反的括號字符，并非相同字符。可以用 switch 判斷三種括號字符，或者三個 if 語句，再或者可以用散列表映射括號關系。

Java：

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack<>();//初始化棧
        for (char b : s.toCharArray()) {
            switch (b) {
                case "(": {
                    stack.push(")");
                    break;
                }
                case "{": {
                    stack.push("}");
                    break;
                }
                case "[": {
                    stack.push("]");
                    break;
                }
                default: {//不匹配的情況返回false
                    if (stack.isEmpty() || stack.pop() != b) {
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty();//棧為空則證明全部匹配，返回true，否則返回false
    }
}

Python:

注：python中沒有 switch...case... 語句，官方讓用 if 判斷代替...

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c == "[":
                stack.append("]")
            elif c == "(":
                stack.append(")")
            elif c == "{":
                stack.append("}")
            elif len(stack) == 0 or stack.pop() != c:
                return False
        return len(stack) == 0

歡迎關注微信公.眾號：愛寫Bug

云服務器 GPU云服務器 Parentheses LeetCode python中的括號 html向下的括號

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/75768.html

[Leetcode] Longest Valid Parentheses 最長有效括號對

摘要：假設是從下標開始到字符串結尾最長括號對長度，是字符串下標為的括號。如果所有符號都是，說明是有效的。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses...

everfight 2019-08-14 16:11 評論0 收藏0
[Leetcode] Valid Parentheses 驗證有效括號對

摘要：如棧中是，來一個變成，再來一個，變成。注意棧在或者操作之前要驗證非空，否則會拋出。代碼最后要判斷棧的大小，如果循環結束后棧內還有元素，說明也是無效的代碼 Valid Parentheses Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is...

zhkai 2019-08-14 16:11 評論0 收藏0
LeetCode 之 JavaScript 解答第20題 —— 有效的括號（Valid Parent

摘要：小鹿題目給定一個只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號必須用相同類型的右括號閉合。注意空字符串可被認為是有效字符串。除去這兩種情況都不是符合條件的。 Time：2019/4/11Title: Valid ParenthesesDifficulty: EasyAuthor: 小鹿題目：Valid Parentheses Given a string c...

novo 2019-08-23 16:54 評論0 收藏0
Leetcode20 - Valid Parentheses

摘要：第一反應是用棧，然后將左括號入棧，右括號出棧，遍歷結束后看看是不是?？樟?。但是由于頻繁的函數調用，導致時間效率不如第一個。但是第一個的方法更容易出錯。 Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid. The br...

iOS122 2019-08-14 12:10 評論0 收藏0
[leetcode]Longest Valid Parentheses

摘要：在問題中，我們可以用來檢驗括號對，也可以通過來檢驗。遇到就加一，遇到就減一。找到一對括號就在最終結果上加。我們用來表示當前位置的最長括號。括號之間的關系有兩種，包含和相離。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the lon...

qujian 2019-08-14 16:53 評論0 收藏0