Simple but efficient iterative Swift solution


  • 0
    V
        func generateParenthesis(_ n: Int) -> [String] {
            // count is the number of open parenthesis minus the number of close parenthesis
            // in the partialString
            typealias PartialResult = (partialString: String, count: Int)
            var prior = [PartialResult]()
            var current = [PartialResult]()
            prior.append(("", 0))
            
            // Simple iteration, prior holds all possible partial results of size index - 1
            // we accumulate all partial results of size index in current
            // We run 2 * n iterations because we have to place n open parenthesis and n close parenthesis
            for index in 1...(2 * n) {
                for instance in prior {
                    // The number of remaining parenthesis to add is 2 * n - index, if count equals that
                    // everything else needs to be a close parenthesis
                    if instance.count < 2 * n - index {
                        current.append((instance.partialString.appending("("), instance.count + 1))
                    }
                    
                    // If count is 0 there are no unclosed parenthesis in the partialString so we can only
                    // add an open parenthesis at this point
                    if instance.count > 0 {
                        current.append((instance.partialString.appending(")"), instance.count - 1))
                    }
                }
                
                prior = current
                current = [PartialResult]()
            }
            
            return prior.map({ $0.partialString })
        }
    

    Just wanted to share a simple but efficient iterative approach in Swift. Basically for possible string of length i - 1 we add a ( or ) parenthesis where appropriate. It's easy to keep track of when we can or can not add these by keeping track of the number of "(" - the number of ")" for any given partial solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.