16 -- 删除无效的括号

题目

Github链接

• 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
  返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：
输入：s = “()())()”
输出：[“(())()”,“()()()”]
示例 2：
输入：s = “(a)())()”
输出：[“(a())()”,“(a)()()”]
示例 3：
输入：s = “)(”
输出：[“”]

• 思路

1. 先求出"(“多出的个数left 和”)"多出的个数right
2. 再挨个删除，比如多出了两个"(“，一个”(“，所有的情况，只能是挨个删除，先删除第一个”(“，再继续递归，再删除第二个”(“，再递归，删除”)"，当left和right等于0，并且字符串符合要求，就加入答案中。

代码如下

//
//  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.遍历左右两边的括号多余的数量
        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 { // ")))" -- 要没有添加元素了
                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]
    }
}