LeetCode 20. 有效的括号 Valid Parenth

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

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

【示例1】

输入: "()"
输出: true

【示例2】

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

【示例3】

输入: "(]"
输出: false

【示例4】

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

【示例5】

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

【思路1】
1、使用库函数
2、使用空串替换 () [] {}任意出现的字符对
3、如果最后字符串长度为0，那么返回true 否则返回false
4、时间复杂度O(n^2)，时间比较差

Swift代码实现：

func isValid(_ s: String) -> Bool {
    if s.count == 0 { return true }
    var tmp = s
    while tmp.contains("()") || tmp.contains("{}") || tmp.contains("[]") {
        tmp = tmp.replacingOccurrences(of: "()", with: "")
        tmp = tmp.replacingOccurrences(of: "{}", with: "")
        tmp = tmp.replacingOccurrences(of: "[]", with: "")
    }
    return tmp.count == 0
}

【思路2】
1、使用栈或者数组
2、如果是左括号( { [，装进数组或进栈
3、如果是右括号) } ]，判断指针index 如果小于等于0 返回false ，因为第一个就是右括号) } ]，如果index大于0，判断当前字符和数组最后一个字符或栈顶字符是否是左括号( { [，如果是删除数组最后一个字符或pop栈顶元素；index--；
4、遍历s完成后 判断栈或数组是否为空，为空返回true 否则返回false
5、时间复杂度O(n)
6、空间复杂度O(n)

Swift代码实现：

func isValid(_ s: String) -> Bool {
    if s.count == 0 { return true }
    var chaArr = [Character]()
    var index = 0
    for c in s {
        if c == "(" || c == "{" || c == "[" {
            chaArr.append(c)
            index+=1
        } else {
            if index <= 0 {
                return false
            }
            let tmp = (c == ")" && chaArr[index-1] == "(") || (c == "]" && chaArr[index-1] == "[") || (c == "}" && chaArr[index-1] == "{")
            if tmp {
                chaArr.removeLast()
            }
            index-=1
        }
    }
    return chaArr.count == 0
}