給定一個只包含三種字符的字符串：（ ，） 和 *，寫一個函數(shù)來檢驗這個字符串是否為有效字符串。
有效字符串具有如下規(guī)則：
①任何左括號 ( 必須有相應的右括號 )。
②任何右括號 ) 必須有相應的左括號 ( 。
③左括號 ( 必須在對應的右括號之前 )。
* 可以被視為單個右括號 ) ，或單個左括號 ( ，或一個空字符串。
一個空字符串也被視為有效字符串。

例如:

輸入: "()"
輸出: True

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

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

棧方法

先注意下 * 可以被視為單個右括號 ) ，或單個左括號 ( ，或一個空字符串

1.針對于特殊情況做處理 (不過我的確沒料到 "*", "" 這種都也算true...)

2.創(chuàng)建2個容器, 1個用于存儲 "(", 1個用于存儲 "*"。
留意下, 這里我們是以 s對應字符下標做key, s對應字符為value存儲(字典形式存儲), 因為后邊會用到下標

3.for循環(huán)s,
① 如果是 "(" 以字典形式 "下標:值" 入棧(result)
② 如果是 "*" 以字典形式 "下標:值" 入棧(temp)
③ 如果是 ")"
(1).result元素個數(shù) > 0 "(" 出棧(result)
(2).result元素個數(shù) == 0 并且 temp元素個數(shù) > 0 "*" 出棧(temp), 因為*可以作為 "("
(3).result, temp都為0, 返回, 應為不能形成閉合括號

4.for結束, 應該只剩下 result, temp數(shù)組,
由于 *可以作為")", 所以我們循環(huán)result數(shù)組
① temp 元素個數(shù)為0, result不為0, 直接 false, 因為剩下的就是"("形不成閉合括號
② temp 最大值下標 < result 最大值下標, 直接 false, 因為"*(" 這種形不成閉合括號
③ 都滿足, "(" 出棧, "*" 出棧, 繼續(xù)循環(huán)

5.因為4中循環(huán)條件是 result.count > 0,
所以循環(huán)結束出來的 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 算法合集地址