LeetCode20. 有效的括号（Swift）

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例：

示例 1:
输入: "()"
输出: true

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

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

简单思路：
1，匹配不同类别的括号,所以把所有类型写在字典里
[ "(": ")", "{":"}", "[":"]" ]

2,在遍历目标字符串字符的循环中，用栈或者数组储存"左"括号，遇到同类别“右”括号，则pop

3,最后检查栈或者数组是否为空，为空则是有效字符，否则是无效字符

注意：空字符，直接返回true（原因：题目里面已经说明了）

代码：
方式一：数组

class Solution {

    func isValid(_ s: String) -> Bool {

        if s.isEmpty {
            return true
        }
        
        let mapping = [ "(": ")", "{":"}", "[":"]" ]
        var array = [String]()
        
        // 遍历字符串
        for character in s {
            let str = String(character)
            
            if mapping.keys.contains(str){
                // 左括号，加入数组中（注意，要加入数组尾部，不能插入到头部，数组是一组连续的内存空间，如果在头部插入数据，后面所有数据的内存地址都要向后移，增加空间复杂度）
                array.append(str)
            }else {
                //
                guard let lastStr = array.last, str == mapping[lastStr] else {
                    return false
                }
                
                // 与数组最后一位匹配括号，匹配上则pop
                array.popLast()
            }            
        }
     
        return array.isEmpty
    }
}

方式二：栈

class Solution {
    struct Stack<T>{
        fileprivate var array = [T]()
        
        var count:Int {
            return array.count
        }  
        var isEmpty: Bool {
            return array.isEmpty
        }        
        var top : T? {
            return array.last
        }       
        
        mutating func push(newElement:T) {            
           
            array.append(newElement)         
        }
        
        mutating func pop() -> T? {
            if isEmpty {
                return nil
            }
            return array.popLast()
        }
    }
    func isValid(_ s: String) -> Bool {
        if s.isEmpty {
            return true
        }
        
        let mapping:[Character:Character] = [ "(": ")", "{":"}", "[":"]" ]
        var stack = Stack<Character>()
        
        for character in s {
            
            if mapping.keys.contains(character) {
                stack.push(newElement: character)
            }else {
                guard let lastStr = stack.top, character == mapping[lastStr]  else {
                    return false
                }
                
                stack.pop()
            }
        }
        
        return stack.isEmpty
    }
}