資訊專欄INFORMATION COLUMN
摘要：給定一個(gè)只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號(hào)必須用相同類型的右括號(hào)閉合。注意空字符串可被認(rèn)為是有效字符串。
給定一個(gè)只包括 "("，")"，"{"，"}"，"["，"]" 的字符串，判斷字符串是否有效。
Given a string containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.
有效字符串需滿足：
左括號(hào)必須用相同類型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
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.
注意空字符串可被認(rèn)為是有效字符串。
Note that an empty string is also considered valid.
示例 1:
輸入: "()" 輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]" 輸出: false
示例 4:
輸入: "([)]" 輸出: false
示例 5:
輸入: "{[]}"
輸出: true
解題思路：
很簡(jiǎn)單的題，將字符串每個(gè)字符壓入棧，簡(jiǎn)單判斷即可。如：
輸入: "{[]}"
初始棧為空，"{" 入棧
下一個(gè)字符
棧頂元素 "{"與 "[" 不匹配，"[" 入棧
下一個(gè)字符
棧頂元素 "["與 "]" 匹配，"[" 出棧
下一個(gè)字符
棧頂元素 "{"與 "}" 匹配，"}" 出棧
結(jié)束，棧為空，返回 True
關(guān)鍵在于判斷字符是否匹配，匹配的標(biāo)準(zhǔn)是相反的括號(hào)字符，并非相同字符?？梢杂?switch 判斷三種括號(hào)字符，或者三個(gè) if 語(yǔ)句，再或者可以用散列表映射括號(hào)關(guān)系。
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... 語(yǔ)句，官方讓用 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
歡迎關(guān)注微信公.眾號(hào)：愛寫B(tài)ug
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/75768.html
摘要：假設(shè)是從下標(biāo)開始到字符串結(jié)尾最長(zhǎng)括號(hào)對(duì)長(zhǎng)度，是字符串下標(biāo)為的括號(hào)。如果所有符號(hào)都是，說(shuō)明是有效的。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses...
摘要：如棧中是，來(lái)一個(gè)變成，再來(lái)一個(gè)，變成。注意棧在或者操作之前要驗(yàn)證非空，否則會(huì)拋出。代碼最后要判斷棧的大小，如果循環(huán)結(jié)束后棧內(nèi)還有元素，說(shuō)明也是無(wú)效的代碼 Valid Parentheses Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is...
摘要：小鹿題目給定一個(gè)只包括，，，，，的字符串，判斷字符串是否有效。有效字符串需滿足左括號(hào)必須用相同類型的右括號(hào)閉合。注意空字符串可被認(rèn)為是有效字符串。除去這兩種情況都不是符合條件的。 Time：2019/4/11Title: Valid ParenthesesDifficulty: EasyAuthor: 小鹿 題目：Valid Parentheses Given a string c...
摘要：第一反應(yīng)是用棧，然后將左括號(hào)入棧，右括號(hào)出棧，遍歷結(jié)束后看看是不是棧空了。但是由于頻繁的函數(shù)調(diào)用，導(dǎo)致時(shí)間效率不如第一個(gè)。但是第一個(gè)的方法更容易出錯(cuò)。 Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid. The br...
摘要：在問題中，我們可以用來(lái)檢驗(yàn)括號(hào)對(duì)，也可以通過來(lái)檢驗(yàn)。遇到就加一，遇到就減一。找到一對(duì)括號(hào)就在最終結(jié)果上加。我們用來(lái)表示當(dāng)前位置的最長(zhǎng)括號(hào)。括號(hào)之間的關(guān)系有兩種，包含和相離。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the lon...
閱讀 2020·2023-04-25 22:50
閱讀 2834·2021-09-29 09:35
閱讀 3390·2021-07-29 10:20
閱讀 3153·2019-08-29 13:57
閱讀 3356·2019-08-29 13:50
閱讀 3032·2019-08-26 12:10
閱讀 3530·2019-08-23 18:41
閱讀 2634·2019-08-23 18:01
