16 -- remove invalid parentheses

subject

Github link

• Here's a string of parentheses and letters s , Remove the minimum number of invalid parentheses , Make the input string valid .
  Returns all possible results . You can press In any order return .

Example 1：
Input ：s = “()())()”
Output ：[“(())()”,“()()()”]
Example 2：
Input ：s = “(a)())()”
Output ：[“(a())()”,“(a)()()”]
Example 3：
Input ：s = “)(”
Output ：[“”]

• Ideas

1. Find out first "(“ The number of extra left and ”)" The number of extra right
2. Delete one by one , For example, there are two more "(“, One ”(“, In all cases , It can only be deleted one by one , First delete the first ”(“, Continue recursion , Delete the second ”(“, Re recursion , Delete ”)", When left and right be equal to 0, And the string meets the requirements , Just add it to the answer .

The code is as follows

//
//  facebook04.swift
//  ForDreams
//
//  Created by cao hua on 2022/6/25.
//

import Foundation

class facebook04 {
    //s = "()())()"
    //s = "(')'())()"
    //    "()()')'()"
    var res = [String]()
    
    func removeInvalidParentheses(_ s: String) -> [String] {
        // 1. Traverse the number of left and right parentheses 
        let left = getLRCount(s).first! // 0
        let right = getLRCount(s).last! // 1
        
        //
        helper(s, 0, left, right)
        
        return res
    }
    
    private func getLRCount(_ s: String) -> [Int] {
        var left = 0
        var right = 0
        
        for c in s {
            if String(c) == "(" {
                left += 1
            } else if String(c) == ")" {
                if left == 0 {
                    right += 1
                } else {
                    left -= 1
                }
            }
        }
        
        return [left, right]
    }
    
    private func helper(_ s: String, _ start: Int, _ left: Int, _ right: Int) {
        if left == 0 && right == 0 {
            if isValid(s) {
                res.append(s)
            }
            return
        }
        
        for i in start..<s.count {
            if i != start && s.charAt(i) == s.charAt(i - 1) {
                continue
            }
            
            if left + right > s.count - i { // ")))" --  No more elements to be added 
                return
            }
            
            if left > 0 && s.charAt(i) == "(" {
                let tempArr = Array(s)
                let pre = String(tempArr[0..<i])
                let post = String(tempArr[(i+1)..<s.count])
                let tempStr = pre + post
                helper(tempStr, i, left - 1, right)
            }
            
            if right > 0 && s.charAt(i) == ")" {
                let tempArr = Array(s)
                let pre = String(tempArr[0..<i])
                let post = String(tempArr[(i+1)..<s.count])
                let tempStr = pre + post
                helper(tempStr, i, left, right - 1)
            }
        }
    }
    
    private func isValid(_ s: String) -> Bool {
        var cnt = 0
        for c in s {
            if String(c) == "(" {
                cnt += 1
            } else if String(c) == ")" {
                cnt -= 1
                if cnt < 0 {
                    return false
                }
            }
        }
        
        return cnt == 0
    }
}

extension String {
    func charAt(_ index: Int) -> Character {
        let tempArr = Array(self)
        return tempArr[index]
    }
}