LeetCode22 生成所有括号对

2019/04/10 10:10
阅读数 7

本文始发于个人公众号:TechFlow,原创不易,求个关注

<br>

链接

Generate Parentheses

<br>

难度

<font color=orange>Medium</font>

<br>

描述

<br>

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

给定n对括号,要求返回所有这些括号组成的不同的合法的字符串

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

<br>

题解

<br>

这道题目非常有意思,解法也很多,还是老规矩,我们先由易到难,先从最简单的方法开始入手。

我们来简单分析一下题目,n个括号对意味着字符串的长度是2n,我们利用排列组合可以计算出,所有的组合种数一共有$C_{2n}^n$种。算一下会知道,这个数是很大的,也就是说我们哪怕一开始就知道答案,把答案遍历一遍也会有很高的耗时,所以这道题对于时间复杂度的要求应该不会很高。

<br>

暴力

<br>

能想到最简单的方法,当然是暴力,不要看不起这个朴素的算法,很多时候灵感都是从暴力当中获取的。但是这道题暴力不太容易写,因为会有一种无从入手的感觉,我们知道要暴力,但是并不知道应该怎样暴力。这道题不存在可以直接枚举的朴素元素,必须要我们拐个弯才行。

怎么拐弯呢,其实答案我刚才已经说出来了。n个括号对,也就是说一共2n个字符,我们可以枚举n个'('分别放在什么位置,剩下的自然就是')'了。看起来很有道理,但是有一个问题,就是这个思路并没有办法通过循环直接实现。这其实已经进化成了一个搜索问题了,我们要搜索所有可以摆放括号的可能性。

如果你能从暴力方法跳跃到搜索问题,那么说明你离写出代码已经很接近了。如果不行,那么我建议你花点时间去学习一下搜索算法专题。

对于搜索问题而言,这已经很简单了,我们搜索的空间是明确的,2n个位置,搜索的内容,对于每个位置我们可以摆放'('也可以摆放')'。那么代码自然而然呼之欲出:

def dfs(pos, left, right, n, ret, cur_str):
    """
    pos: 当前枚举的位置
    left: 已经放置的左括号的数量
    right: 已经放置的右括号的数量
    n: 括号的数量
    ret: 放置答案的数组
    cur_str: 当前的字符串
    """
    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+')')

这个程序遍历运行之后还没有结束,我们还需要判断生成出来的括号是否合法,也就是说括号需要匹配上。我们可以用一个栈来判断括号是否能够匹配,比如我们遇见左括号就进栈,遇见右括号则判断栈顶,如果栈顶是左括号,那么栈顶的左括号出栈,否则则入栈,最后判断栈是否为空。这个算法实现当然不难,但是如果你仔细去想了,你会发现完全没有必要用栈,因为如果我们遇到右括号的时候,栈顶不为左括号,那么一定最后是无法匹配的。因为后面出现的左括号不能匹配前面出现的右括号,正所谓往者不可追就是这个道理。【狗头】

<br>

优化

<br>

我们来思考一个问题:什么情况会出现右括号遇不到左括号呢?只有一种情况,就是当前出现右括号的个数超过了左括号,也就是说我们遍历一下字符串,如果中途出现右括号数量超过左括号的情况,那么就说明这个字符串是非法的。看起来没毛病对吧,但是有问题,我们为什么不在枚举的时候就判断呢,如果左括号放入的数量已经等于右括号了,那么就不往里防止右括号,这样不就可以保证搜索到的一定是合法的字符串吗?

如果你能想到这一层,说明你对搜索的理解已经很不错了。我们看一下改动之后的代码:

def dfs(pos, left, right, n, ret, cur_str):
    """
    pos: 当前枚举的位置
    left: 已经放置的左括号的数量
    right: 已经放置的右括号的数量
    n: 括号的数量
    ret: 放置答案的数组
    cur_str: 当前的字符串
    """
    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+')')

大部分代码都没有变化,只是在right < n后面加入了一个right < left这个条件。看似只有一个条件,但是这个条件起到的作用至关重要。整个算法的效率有了质的提升,实际上这也是效率最高的算法。

<br>

构造

<br>

上面的方案在LeetCode官方当中都有收入,也是比较常规的解法,下面要介绍的方法是我的原创,我个人感觉也比较有意思,分享给大家。

在之前的文章当中我们介绍过分治法,分治法的核心是将一个看似无法求解的大问题,分解成比较容易解决的小问题,最后加以解决。这道题当中,我们直接求n时的解法是比较困难的,没办法直接获得,我们能不能也试着使用分治的方法来解决呢?

我们来观察一下数据,当n=1的时候,很简单,结果是(),只有这一种。当n=2呢?有两种,分别是(())和()(),当n=3呢?有5种:((())), ()(()), ()()(), (()()), (())()。这当中有没有规律呢?

我们用solution(n)表示n对应的解法,那么我们可以写出solution(n)对应的公式:

$$solution(n) = \sum_{i=1}^{n-1} solution(i)+solution(n-i) + ( + solution(n-1) + )$$

上面这个式子有点像是动态规划的状态转移方程,虽然不完全一样,但是大概是那么回事。也就是说我们可以用比答案规模小的答案组装成现在的答案。比如n=3时的答案,等于n=2时的答案和n=1时答案的拼接。

比如: solution(1) + solution(2) 可以得到: ()()()和()(()),solution(2) + solution(1)可以得到 ()()()和(())()。但是还有一种答案无法通过拼接得到就是( solution(2) )。也就是说在solution(2)的答案外面包一层括号。那为什么不用考虑solution(1)的答案外面包两层括号呢?答案很简单,因为solution(2)已经包括了这样的情况,所以我们只用往下考虑一层。

不过还没有结束,还有一点小问题,就是这样得到的答案可能会有重复,所以我们需要去重,利用set我们可以很简单做到这点,让我们一起来看代码:

class Solution:
            
    def generateParenthesis(self, n: int) -> List[str]:
        solutionMap = {}
        # 记录下n=0和1时的答案
        solutionMap[0] = set([""])
        solutionMap[1] = set(["()"])

        # 遍历小于n的所有长度
        for i in range(2, n+1):
            cur = set()
            # 遍历小于n的所有长度
            for j in range(1, i):
                # 构造答案
                ans1 = solutionMap[j]
                ans2 = solutionMap[i-j]
                for s in ans1:
                    for t in ans2:
                        cur.add(s + t)
            # 构造 ( solution(n-1) )这种答案
            for s in solutionMap[i-1]:
                cur.add("(" + s + ")")
            solutionMap[i] = cur
        return list(solutionMap[n])

在C++当中,这两种方法的效率差不多,但是使用Python的话,构造的方法要更快一些。和搜索这种方法相比,搜索是不知道答案去搜寻答案,而构造法是知道答案大概长什么样子,依据一定的规则生产答案。可以说是两种不同思路的解法,也是我本人很喜欢这道题的原因。

这道题的代码都不长,但是思路挺有意思,希望大家会喜欢。

今天的文章就是这些,如果觉得有所收获,请顺手扫码点个关注吧,你们的举手之劳对我来说很重要。

原文出处:https://www.cnblogs.com/techflow/p/12315714.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部