IOS 算法(中级篇) ----- 有效的括号字符串

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。
有效字符串具有如下规则：
①任何左括号 ( 必须有相应的右括号 )。
②任何右括号 ) 必须有相应的左括号 ( 。
③左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

例如:

输入: "()"
输出: True

输入: "(*)"
输出: True

输入: "(*))"
输出: True

栈方法

先注意下 * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串

1.针对于特殊情况做处理 (不过我的确没料到 "*", "" 这种都也算true...)

2.创建2个容器, 1个用于存储 "(", 1个用于存储 "*"。
留意下, 这里我们是以 s对应字符下标做key, s对应字符为value存储(字典形式存储), 因为后边会用到下标

3.for循环s,
① 如果是 "(" 以字典形式 "下标:值" 入栈(result)
② 如果是 "*" 以字典形式 "下标:值" 入栈(temp)
③ 如果是 ")"
(1).result元素个数 > 0 "(" 出栈(result)
(2).result元素个数 == 0 并且 temp元素个数 > 0 "*" 出栈(temp), 因为*可以作为 "("
(3).result, temp都为0, 返回, 应为不能形成闭合括号

4.for结束, 应该只剩下 result, temp数组,
由于 *可以作为")", 所以我们循环result数组
① temp 元素个数为0, result不为0, 直接 false, 因为剩下的就是"("形不成闭合括号
② temp 最大值下标 < result 最大值下标, 直接 false, 因为"*(" 这种形不成闭合括号
③ 都满足, "(" 出栈, "*" 出栈, 继续循环

5.因为4中循环条件是 result.count > 0,
所以循环结束出来的 result 都为0, *剩下无所谓, 可做一个空字符. 既然是闭合括号字符串, 直接true返回即可

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

        if s.count == 0 || s == "*" { return true }
        if s.count == 1  { return false }

        var result:[[Int:Character]] = [], temp:[[Int:Character]] = []
    
        for (index, item) in s.enumerated() {
           
            if item == "(" {
                result.append([index:item])
            }else if item == "*" {
                temp.append([index:item])
            }else if item == ")" {
                if result.count > 0 {
                    result.removeLast()
                }else if result.count == 0 && temp.count > 0{
                    temp.removeLast()
                }else if result.count == 0 && temp.count == 0{
                    return false
                }
            }
        }

        while result.count > 0 {
            
            if temp.count == 0 {
                return false
            }
            
            let last1 = result.last!.keys.first!
            let last2 = temp.last!.keys.first!
            
            if last1 > last2 {
                return false
            }
            
            result.removeLast()
            temp.removeLast()

        }
        
        return true
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址