This is 13 days of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021 “.

preface

I have been planning to learn data structures and basic algorithms, but I have seen them in fits and starts. Now I’m determined to stick to it. I’m going to start with LeetCode’s HOT100 and finish 1~2 exercises every day, hoping to develop the habit of continuous learning in this way. Because I am doing iOS development, mainly using Objective-C language, and I am also learning Swift recently, all the questions in this series will be solved using Swift language. What is updated in this paper is the generation of parenthesis 022 of question 13 of HOT100 in LeetCode.

The title

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations. The combination of valid brackets must meet the following requirements: The left bracket must be closed in the correct sequence. Example 1:

Input: n = 3 output: [" ((())) ", "() () ()", "() () ()", "() () ()", "() () ()"]Copy the code

Example 2:

Output: ["()"]Copy the code

Tip:

1 <= n <= 8
Copy the code

Analysis of the

The purpose of this question is to generate a valid combination of pairs of parentheses. Only the parentheses “()” are included, and no other parentheses are included. N represents the logarithm of parentheses generated, so the total length of the string is 2∗n2*n2∗n, and each character can only be one of “(” and “)”. We can generate all 22N sequences of ‘(‘ and ‘)’ characters, and then we can check if each one is valid. To generate all the sequences, we can use recursion. A sequence of length n is preceded by a ‘(‘ or ‘)#### backtrace ‘to a sequence of length n-1. To check if the sequence is valid, we can use LeetCode’s HOT100–020 valid parenthesis idea that we did earlier, and just iterate through it once. The complexity of this method is O(n*22n). Backtracking violence can be improved by adding ‘(‘ or ‘)’ only when the sequence is still valid, rather than adding ‘(‘ and ‘)’ mindlessly to each digit. We can do this by keeping track of the number of open and close parentheses placed so far. If the number of open parentheses is not greater than n, we can put an open parenthesis. If the number of close parentheses is less than the number of open parentheses, we can put a close parentheses. In this way, we can directly generate a matching pair of parentheses through recursive backtracking without any judgment. This reduces complexity.

Answer key

class KLLC022 {
    func generateParenthesis(_ n: Int)- > [String] {
        if n = = 0 {
            return [String]()
        }
        // Initialize the result set to be empty. The current string has only 1 open parenthesis
        var result = [String] ()var curStr = "("
        dfs(&curStr, 1.0, n, &result)
        return result
    }
    
    / / back method
    //curStr current string
    //leftCount The number of left parentheses in the current string
    RightCount The number of close parentheses in the current string
    //n parentheses logarithm
    //result Specifies the result set that meets the condition
    func dfs(_ curStr:inout String._ leftCount:Int._ rightCount:Int._ n:Int._ result:inout [String]){
        // If the current string length is 2*n, then the string over is stored in the result set
        if curStr.count = = (2 * n) {
            let ans = curStr
            result.append(ans)
            return
        }
        // If the number of open parentheses is less than n, then the current bit can be placed in the open parenthesis
        if leftCount < n {
            // The current bit is stored as an open parenthesis for the next bit recursion
            curStr.append("(")
            dfs(&curStr, leftCount + 1, rightCount, n, &result)
            // Delete the parentheses stored in the current bit, and perform other operations on the current bit
            curStr.removeLast()
        }
        // If the number of close parentheses is less than the number of close parentheses, then the current bit can be placed in the close parentheses
        if rightCount < leftCount {
            // Save the current bit as close parenthesis for the next bit recursion
            curStr.append(")")
            dfs(&curStr, leftCount, rightCount + 1, n, &result)
            // Delete the parentheses stored in the current bit, and perform other operations on the current bit
            curStr.removeLast()
        }
    }
}
Copy the code