leetcode 20 Valid Parentheses

qiangdada 發(fā)布于2019-08-19 10:41 / 1398人閱讀

摘要：判定是否有效的一句就是，字符必須嚴格有序。例如和是有效的，但是和就是無效的。對于前一半字符，我們對它們進行入棧操作。如果不匹配，即整個字符串無效。當整個字符串的遍歷結束的時候，判斷棧是否為空完全匹配。

題目詳情

Given a string containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.輸入一個字符串s，這個字符串是由字符"(", ")", "{", "}", "[" 和 "]"組成的。我們需要判定這個字符串的格式是否有效。判定是否有效的一句就是，字符必須嚴格有序。例如"()" 和 "()[]{}"是有效的，但是"()"和"()[]{}"就是無效的。

想法

這道題目比較適合用棧作為存儲中間結果的數據結構，因為字符應當是后進先出，方便我們進行判斷。

對于前一半字符(eg.‘(’,"[","{")，我們對它們進行入棧操作。

如果遇到了后半字符，我們需要對棧頂元素取出，并判斷棧頂字符和當前字符是否匹配。如果不匹配，即整個字符串無效。

當整個字符串的遍歷結束的時候，判斷棧是否為空（完全匹配）。

解法

        Stack save = new Stack();
        if(s.length() == 0)return true;
        
        for(char c : s.toCharArray()){
            if(c == "("){
                save.push(")");
            }else if (c == "["){
                save.push("]");
            }else if (c == "{"){
                save.push("}");
            }else if (save.isEmpty() || c != save.pop()){
                return false;
            }
        }
        
        return save.isEmpty();

云服務器 GPU云服務器 Parentheses Leetcod Valid LeetCode

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

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

LeetCode 20：有效的括號 Valid Parentheses

摘要：給定一個只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號必須用相同類型的右括號閉合。注意空字符串可被認為是有效字符串。給定一個只包括 (，)，{，}，[，] 的字符串，判斷字符串是否有效。 Given a string containing just the characters (, ), {, }, [ and ], determine if the inpu...

TesterHome 2019-08-19 10:17 評論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
[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] 32. Longest Valid Parentheses

Problem Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: (()Output: 2Explanation: The longest valid pa...

Flink_China 2019-08-19 11:14 評論0 收藏0