LeetCode之有效的括號
作者：Swift君
描述給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。使用堆棧查看 peek 左大括號是否對應于當前右大括號。
前言
我們社區陸續會將顧毅(Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。微博:@故胤道長[1])的 Swift 算法題題解整理為文字版以方便大家學習與閱讀。
LeetCode 算法到目前我們已經更新了 19 期，我們會保持更新時間和進度(周一、周三、周五早上 9:00 發布)，每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。
不積跬步，無以至千里;不積小流，無以成江海，Swift社區 伴你前行。
難度水平：簡單
1. 描述
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
2. 示例
示例 1
輸入：s = "()"
輸出：true
示例 2
輸入：s = "()[]{}"
輸出：true
示例 3
輸入：s = "(]"
輸出：false
示例 4
輸入：s = "([)]"
輸出：false
示例 5
輸入：s = "{[]}"
輸出：true
約束條件：
- 1 <= s.length <= 104
- s 僅由括號 '()[]{}' 組成
3. 答案
class ValidParentheses {
func isValid(_ s: String) -> Bool {
var stack = [Character]()
for char in s {
if char == "(" || char == "[" || char == "{" {
stack.append(char)
} else if char == ")" {
guard stack.count != 0 && stack.removeLast() == "(" else {
return false
}
} else if char == "]" {
guard stack.count != 0 && stack.removeLast() == "[" else {
return false
}
} else if char == "}" {
guard stack.count != 0 && stack.removeLast() == "{" else {
return false
}
}
}
return stack.isEmpty
}
}
- 主要思想：使用堆棧查看 peek 左大括號是否對應于當前右大括號。
- 時間復雜度：O(n)
- 空間復雜度：O(n)
該算法題解的倉庫：LeetCode-Swift[2]
點擊前往 LeetCode[3] 練習
參考資料
[1] @故胤道長: https://m.weibo.cn/u/1827884772
[2] LeetCode-Swift: https://github.com/soapyigu/LeetCode-Swift
[3] LeetCode: https://leetcode.com/problems/valid-parentheses
責任編輯：姜華
來源：
Swift社區
