[Swift]LeetCode20.有效的括号|ValidParentheses

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9697906.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

 1 class Solution {
 2     func isValid(_ s: String) -> Bool {
 3         //字符串为空返回true
 4         if s.isEmpty
 5         {
 6             return true
 7         }
 8         else
 9         {
10             //或字符串的字符个数为奇数个直接排除
11             if s.count%2==1
12             {
13                 return false
14             }
15         }
16         //创建字典对照表
17         var map:[Character:Character]=[")":"(","}":"{","]":"["]
18         //偶数符串若第一个字符就是右边的符号则直接排除
19         if  map[s[s.startIndex]] != nil
20         {
21             return false
22         }
23         //创建字符串堆栈
24         var stackOfString=Stack<Character>()
25         //遍历字符串
26         for char in s
27         {
28             //为右侧符号，且查询字典对应堆栈中最后一个元素
29             if map[char] != nil && map[char]==stackOfString.GetLastElement()
30             {
31                 //出栈
32                 stackOfString.pop()
33             }
34             else
35             {
36                 //入栈
37                 stackOfString.push(char)
38             }
39         }
40         return stackOfString.count()==0
41     }
42     //堆栈的泛型通用版本
43     struct Stack<Element> {
44         var items = [Element]()
45         //入栈
46         //mutating 关键字修饰方法是为了能在该方法中修改 struct 或是 enum 的变量
47         mutating func push(_ item: Element) {
48             items.append(item)
49         }
50         //出栈
51         mutating func pop() -> Element {
52             return items.removeLast()
53         }
54         //返回堆栈中的元素个数
55         mutating func count()->Int
56         {
57             return items.count
58         }
59         //获取最后一个元素
60         mutating func GetLastElement()->Element
61         {
62             return items[items.count-1]
63         }
64     }
65 }

高效率版

 1 class Solution {
 2     func isValid(_ s: String) -> Bool {
 3         var opened = ""
 4         for char in s { 
 5             if char == "(" {
 6                 opened += ")" 
 7             } else if char == "{" {
 8                 opened += "}"
 9             } else if char == "[" {
10                 opened += "]"
11             } else {
12                 if let prevVal = opened.last, prevVal == char {
13                     opened.removeLast()
14                 } else {
15                     return false
16                 }
17             }
18         }
19         return opened.isEmpty
20     }
21 }