This article originated from personal public account: TechFlow, original is not easy, for attention
link
Generate Parentheses
The difficulty
Medium
describe
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Given n pairs of parentheses, it is required to return all the different legal strings made up of these parentheses
For example, given n = 3, a solution set is:
[" ((())) ", "() () ()", "() () ()", "() () ()", "() () ()"]Copy the code
Answer key
This is a very interesting problem, and there are a lot of ways to do it, and as always, we’ll start with the easy way to do it, the easiest way to do it.
And just to do a little bit of analysis, n pairs of brackets means that the length of the string is 2n, and we can use permutations to figure out that all of the combinations are going to be common
violence
The easiest way to think of it, of course, is violence, don’t look down on this simple algorithm, a lot of times inspiration comes from violence. But it’s not easy to write about violence, because there’s a sense that we don’t know where to start, that we know violence, but we don’t know how to be violent. There are no naive elements that can be directly enumerated, so we have to take a detour.
How to turn the corner? Actually, I already said the answer. N pairs of parentheses, that is, 2n characters, we can enumerate n ‘(‘ in which position, the rest of course is ‘)’. It seems reasonable, but the problem is that there is no way to implement this idea directly through a loop. This has really evolved into a search problem, where we search for all the possibilities for putting parentheses.
If you can jump from violent methods to search problems, you are close to writing code. If not, I suggest you spend some time studying search algorithms.
For a search problem, this is easy enough, we search space is clear, 2n places, search content, for each place we can put ‘(‘ can also put ‘)’. The code comes out naturally:
def dfs(pos, left, right, n, ret, cur_str):
""" pos: current enumeration position left: number of left parentheses that have been placed Right: number of right parentheses that have been placed N: number of parentheses ret: array to place the answer cur_str: current string """
if pos == 2*n:
ret.append(cur_str)
return
if left < n:
dfs(pos+1, left+1, right, n, ret, cur_str+'(')
if right < n:
dfs(pos+1, left, right+1, n, ret, cur_str+') ')
Copy the codeThe program is not finished iterating, and we still need to determine whether the generated parentheses are valid, that is, the parentheses need to match. We can use a stack to determine whether the parentheses match. For example, if we see an open parenthesis, we push it onto the stack, if we see a close parenthesis, we determine the top of the stack. If the top of the stack is an open parenthesis, then the left parenthesis at the top of the stack is pushed off the stack, otherwise, we determine whether the stack is empty. It’s not hard to implement, but if you think about it, you’ll see that there’s no need to use a stack, because if we have a close parenthesis, and the top of the stack is not an open parenthesis, then it’s not going to match. Because the following open parentheses do not match the preceding close parentheses, the so-called past is untraceable. “Dog”
To optimize the
Let’s consider a question: when does a close parenthesis not meet an open parenthesis? There’s only one case where the number of close parentheses is currently greater than the number of open parentheses, which means we’re going through the string, and if the number of close parentheses is greater than the number of open parentheses, then the string is illegal. It doesn’t look bad, but there’s a problem, why don’t we just say, when we enumerate, if the number of open parentheses is equal to the number of close parentheses, then we don’t have to go in to prevent the close parentheses, and then we’re guaranteed to find a valid string?
If you can think of this layer, your understanding of search is pretty good. Let’s look at the changed code:
def dfs(pos, left, right, n, ret, cur_str):
""" pos: current enumeration position left: number of left parentheses that have been placed Right: number of right parentheses that have been placed N: number of parentheses ret: array to place the answer cur_str: current string """
if pos == 2*n:
ret.append(cur_str)
return
if left < n:
dfs(pos+1, left+1, right, n, ret, cur_str+'(')
if right < n and right < left:
dfs(pos+1, left, right+1, n, ret, cur_str+') ')
Copy the codeMost of the code remains the same, except for the right < left condition after right < n. There seems to be only one condition, but this condition plays a crucial role. The efficiency of the whole algorithm has been improved qualitatively, and in fact it is the most efficient algorithm.
structure
All of the above schemes have revenue in the official LeetCode, which is also a relatively conventional solution. The method to be introduced below is my original, and I personally feel it is interesting, so I would like to share it with you.
In the previous article, we introduced the excessive treatment method. The core of the divide-and-conquer method is to decompose a seemingly unsolvable big problem into relatively easy to solve small problems and finally solve them. In this case, it’s hard for us to solve it directly, because we can’t solve it directly, so can we also try to solve it by divide-and-conquer?
So if we look at the data, when n is equal to 1, it’s easy, it’s delta theta, and there’s only one. When n = 2? There are two of them, theta ()) and theta ()(), and what happens when n is equal to 3? There are 5 kinds :(())), ()(()), ()()() ()()()), (()() ())(). Is there a pattern?
We use solution(n) to represent the solution corresponding to n, so we can write the corresponding formula of solution(n) :
This is a little bit like a state transition equation for dynamic programming, not exactly the same, but something like that. That is, we can assemble the current answer from answers that are smaller than the answer. For example, the answer at n=3 is equal to the combination of the answer at n=2 and the answer at n=1.
+ solution such as: solution (1) (2) can be obtained: () () () () () (), and the solution (2) + solution (1) can be () () () and () () (). However, there is another kind of answer that cannot be obtained through splicing (solution(2)). In other words, surround the answer to solution(2) with parentheses. So why not put two brackets around the answer to solution(1)? The answer is simple, because solution(2) already includes such cases, so we only need to consider one layer down.
But we’re not done yet, there’s just one small problem, that is, the answers we get in this way may be duplicated, so we need to de-duplicate them. With set we can do this very easily. Let’s look at the code:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
solutionMap = {}
Write down the answers when n=0 and 1
solutionMap[0] = set([""])
solutionMap[1] = set(["()"])
# Loop over all lengths less than n
for i in range(2, n+1):
cur = set()
# Loop over all lengths less than n
for j in range(1, i):
# Construct the answer
ans1 = solutionMap[j]
ans2 = solutionMap[i-j]
for s in ans1:
for t in ans2:
cur.add(s + t)
# construct (n-1)) such an answer
for s in solutionMap[i- 1]:
cur.add("(" + s + ")")
solutionMap[i] = cur
return list(solutionMap[n])
Copy the codeIn C++, both methods are about as efficient, but in Python, the constructed methods are faster. Compared with the search method, search is to search for the answer without knowing the answer, while the construction method is to know what the answer looks like and produce the answer according to certain rules. It’s two different approaches, and that’s why I like this problem.
It’s not a long code, but it’s interesting, and I hope you’ll enjoy it.
That’s all for today’s article. If you feel you have gained something, please scan the code and pay attention to it. Your contribution is very important to me.
