/ * *
The title
The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations.
Example 1:
Input: n = 3 output: [” ((())) “, “() () ()”, “() () ()”, “() () ()”, “() () ()”] example 2:
Output: [“()”]
Tip:
1 <= n <= 8
Source: LeetCode link: leetcode-cn.com/problems/ge… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
The test code
print(generateParenthesis(3))
notes
The difference between dp[n] and dp[n-1] is that one () has been added to the left side
Such as dp [1] = [[” (“, “) “]] when dp [2]) on a “0” position (“) “, “(“,”) “], plus additional (: [” (“, “) “, “(“,”) “]) in first position [” (“, “) “, “) “], plus additional (is: [” (“, “(“,”) “, “) “]
So dp [2] = [[” (“, “) “, “(“,”) “], [” (“, “(“,”) “, “) “] according to this rule can be concluded that the value of dp [n] Finally, the dp [n] to [String] is the final result
But there will be some repetitive data, in the middle to heavy operation needs to be done Such as: calculate the dp [3] to [” (“, “(“,”) “, “) “] when processing) in the second and third position is [” (“, “(“,” (“, “) “, “) “, “) “]
Optimization idea: dp [0] = [“] dp [1] = [” () “] dp [2] = [” () () “, “(())”]
Or the new (on the left for dp [2]) on a “0” position (+ dp [0] +) + dp [1], the “() ()”) in the first place is (+ dp [1] +) + dp [0], namely “(())”
The resulting formula is dp[n] = (+ every element of dp[I] +) + every element of dp[n-1-i]
For s2 in dp[j] {for s2 in dp[i-j-1] {let tempStr = “(” + s1 + “)” + s2}}
The code address
Github.com/zmfflying/Z… * /
The problem solving code
Import Foundation // func generateParenthesis(_ n: Int) - > [String] {if n = = 1 {return} [" () "] / / the new bracket is split into character to deal with "()" - > [" (", ") "] var dp = [Set<[Character]>].init(repeating: [], count: n+1) dp[1] = [["(",")"]] for i in 2... n { var tempArr:Set<[Character]> = [] for arr in dp[i-1] { for j in 0.. <arr.count {var temp = arr // character) insert into each position temp.insert(")", at:j) Var res:[String] = [String]() for set in dp.last! {let STR = string.init (set[0..<set.count]) res.append(STR)} return res} // generateParenthesis1(_ n: Int) -> [String] { if n == 1 { return ["()"] } var dp = [[String]].init(repeating: [""], count: n+1) dp[1] = ["()"] for i in 2... N {var tempArr:[String] = [] // important dp[n] = (+ dp[I] +) + dp[n-1-i] for j in 0.. <i { for s1 in dp[j] { for s2 in dp[i-j-1] { let tempStr = "(" + s1 + ")" + s2 tempArr.append(tempStr) } } } dp[i] = tempArr } return dp[n] }Copy the code