13 -- remove invalid parentheses

Remove invalid brackets

Github link

• Ideas

1. encounter "(" Push
2. encounter ")“, Check whether the stack is empty , The stack is empty. , Delete the current element
   Stack is not empty. , Then take out the top element of the stack for comparison
   If the elements at the top of the stack can form a pair ”()", Then remove the stack top element
3. After traversal , Look at the elements in the stack
4. When storing stacks , Use a dictionary to store , This will record the index
5. When deleting , Delete from back to front , Do not destroy the structure of the index

class facebook_01 {
    
    //s = "lee(t(c)o)de)" // "a)b(c)d" //"(a(b(c)d)" //"())()(((" "()"
    //"())()((("
    func minRemoveToMakeValid(_ s: String) -> String {
    
        var arr = Array(s).map{
    String($0)}
        var stack = [[Int: String]]()
        
        var left = 0
        while left < arr.count {
    
            if stack.isEmpty {
    
                if arr[left] == ")" {
    
                    arr.remove(at: left)
                } else {
    
                    if arr[left] == "(" {
    
                        let dict = [left: "("]
                        stack.append(dict)
                    }
                    left += 1
                }
            } else {
    
                //  The stack is not empty , Take out the top element of the stack to match , To match , Just delete 
                let topEle = stack[stack.count - 1]
                if topEle.first!.value == "(" && arr[left] == ")" {
    
                    stack.removeLast()
                }
                if arr[left] == "(" {
    
                    let dict = [left: "("]
                    stack.append(dict)
                }
                left += 1
            }
            
        }
        
        if !stack.isEmpty {
    
            for i in (0..<stack.count).reversed() {
    
                arr.remove(at: stack[i].first!.key)
            }
        }
        
        return arr.reduce("", +)
    }
}