T22 括号生成
题目链接:leetcode-cn.com/problems/ge…
思路一:DFS搜索
朴素解法
这是一道典型的「DFS搜索」题目,与之前我们学习过的「电话号码的字母组合」类似,但这里我们会分析得更细致一些。
对于此类题目,为了便于入手,我们不妨先不考虑任何优化,只考虑如下几个问题:
- 搜索的起点在哪里?
- 如何进行搜索?
- 每一个搜索节点下有几条分支?
- 如何判断一条搜索路径是否结束?
对于问题(1),由题意我们知道,想要形成闭合的括号组合,最左侧的括号必须是(
,这就是我们的起点。
对于问题(2),我们只需要从最左侧出发,逐位搜索(实际上是枚举)可能的所有情况即可。
对于问题(3),由于我们这里先不考虑优化,因此每个搜索节点下只有两条分支(即两种可能性):(
、)
。
对于问题(4),根据本题题意我们知道,如果要结束一条搜索路径,无非是碰到了两种情况:①发现搜索到了正确答案;②发现再往下搜索不可能得到正确答案。
我们先考虑前者。
为了表述方便,我们不妨记已搜索到的(
数量为leftNum
,已搜索到的)
为rightNum
。
很显然,只有当leftNum == rightNum == n
时,才说明已经找到了正确的答案。
“等等!仅仅保证左右括号数量相等还不够,还需要保证它们能够一一闭合才对啊!”,如果你现在心中有这个疑惑,非常棒。但请不要着急,先让我们分析后者。
什么时候再往下不可能得到正确答案呢?
首先,题目已经规定了答案中括号对的个数n
,也就是说,倘若我们对每个答案枚举的字符个数超过n * 2
(下记作totalNum
)却发现其不是正确答案,那么该路径必然需要结束。
其次,为了使得所有的括号对都有闭合的机会,必须保证搜索过程中始终有leftNum ≥ rightNum
。
这个条件稍稍有点难度,如果有同学想不明白的话,不妨用「反证法」:
假设leftNum < rightNum
,表明已搜索到的左侧区域必定有多余的)
存在,而此时无论我们如何在右侧区域添加括号(即继续往下搜索),都不可能使前面多余的)
闭合。因此此时搜索到的结果肯定不是正确答案!
现在相信你已经解开了刚才的疑惑。是的,我们只要在搜索的中途将括号无法闭合的情况予以排除,就不需要在校验最终正确答案的时候考虑这个问题了!
现在我们已经分析清楚了这四个问题,下面直接运用我们的老朋友「递归」来实现「DFS搜索」就行了。由于代码比较简单,这里不再仔细讲解。如果你是初次接触此类题目的同学,请尝试找一找刚才的四个问题分别对应代码的哪一部分。
代码如下:
function generateParenthesis(n) {
const ansArr = [];
dfs(n * 2, 1, 0, '(', ansArr);
return ansArr;
}
function dfs(totalNum, leftNum, rightNum, ans, ansArr) {
if (totalNum === leftNum + rightNum) {
leftNum === rightNum && ansArr.push(ans);
}
else if (leftNum >= rightNum) {
dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
}
}
剪枝优化
我们刚才已经编写出了完全不带任何优化的版本,下面我们尝试对其进行「剪枝优化」。
什么是「剪枝优化」呢,从字面上理解,就是在搜索的过程中及时发现并”剪去”搜索树上不可能抵达正确答案的”枝条”。
换句话说,就是我们需要在搜索过程中对一些具体情况进行研判,使得我们尽可能走可能抵达正确答案的搜索路径,规避不可能抵达正确答案的路径。
首先是我们很容易想到的两种情况:
- 当
leftNum = rightNum
时,答案中下一个字符必须是(
; - 当
leftNum + rightNum = totalNum - 1
时,答案中下一个字符必须是)
.
还要其他可以进行剪枝的情况吗?
答案是肯定的。别忘了我们之前分析过,如果要找到正确答案,必须保证搜索过程中不等式leftNum ≥ rightNum
始终成立。那么反过来说,如果走某一条路径会打破这个不等式,那么搜这个路径一定不会得到正确答案!
根据上面的分析,我们优化的代码如下:
function generateParenthesis(n) {
const ansArr = [];
//注意:现在这里若写dfs(n * 2, 0, 0, '', ansArr);也是可以的
//思考:为什么?
dfs(n * 2, 1, 0, '(', ansArr);
return ansArr;
}
function dfs(totalNum, leftNum, rightNum, ans, ansArr) {
if (totalNum === leftNum + rightNum) {
leftNum === rightNum && ansArr.push(ans);
}
//思考:为什么先前代码中的条件leftNum >= rightNum已不再需要?
else {
if (leftNum === rightNum) {
dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
} else if (leftNum + rightNum === totalNum - 1) {
dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
} else {
leftNum + 1 >= rightNum && dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
leftNum >= rightNum + 1 && dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
}
}
}
拓展:从代数角度理解
下面我们来提一下如何从代数角度来理解本题中「DFS搜索」的实现。
我们可以记出现一个(
为得+1
分,出现一个)
为得-1
分。那么对于符合题意的括号组合,都有:
- 当搜索到最终结果时,有总分
score = 0
,即leftNum = rightNum
. 且搜索深度deep = n * 2
,即leftNum + rightNum = totalNum
; - 在搜索过程中,总分始终满足
0 ≤ score ≤ n
,即leftNum ≥ rightNum
且leftNum ≤ n
这两条结论与我们上文中对题意的分析是完全吻合的。
代码如下:
function generateParenthesis(n) {
const ansArr = [];
dfs(n * 2, 1, 1, '(', ansArr);
return ansArr;
}
function dfs(maxDeep, deep, score, ans, ansArr) {
if (deep === maxDeep) {
score === 0 && ansArr.push(ans);
} else {
if (score === 0) {
dfs(maxDeep, deep + 1, score + 1, ans + '(', ansArr);
} else if (deep === maxDeep - 1) {
dfs(maxDeep, deep + 1, score - 1, ans + ')', ansArr);
} else {
score + 1 <= maxDeep/2 && dfs(maxDeep, deep + 1, score + 1, ans + '(', ansArr);
score - 1 >= 0 && dfs(maxDeep, deep + 1, score - 1, ans + ')', ansArr);
}
}
}
思路二:DP动态规划
从观察开始
下面我们思考一个问题:这道题可以用「动态规划」进行解答吗?
我们知道,如果一道题可以用「动态规划」进行解答,那么题目中必须蕴含着某种递推关系。
如果你还没有任何头绪的话,我们可以先来观察一下使用前面「DFS搜索」获得的几组正确答案:
请留意:是不是当n
比较大时的答案,看上去像n
比较小时的答案组装起来的?
为了进一步发掘其中的规律,我们来举一个具体的例子分析一下。
比如当n = 4
时的一个答案'(()())()'
。为了更好地观察,我们拆开来看:'( ()() ) ()'
。
现在一切就很明显了,这个答案看上去应该是在一组新增加的括号内塞了n = 2
时的一个答案()()
,又再它的外面加了n = 1
时的一组答案。我们知道1 + 2 + 1 = 4
,这便是这个n = 4
答案的由来!
递推关系
类似上面的例子还有很多。通过对它们的分析,我们寻找的递推关系也就呼之欲出了:
若规定dp[n]
表示当括号对总数为n
时的任意一个答案,
则有dp[n] = "(" + dp[p] + ")" + dp[q]
,其中p + q + 1 = n
.
代码实现
利用递推关系,我们只需逐一计算从1
到n - 1
的所有正确答案,便能够得到括号对为n
时的答案——因为对每一个dp[n]
中的答案,它都是由前面的dp[n - 1]
中的答案递推(也就是所谓的”组装”)出来的!
代码如下:
function generateParenthesis(n) {
/* 初始化dp数组 */
const dp = [['']];
for(let i = 1; i <= n; i++) dp[i] = [];
/* 动归核心部分 */
for(let curN = 1; curN <= n; curN++) {
for(let p = 0; p < curN; p++) {
let q = curN - p - 1;
//由于dp[n]中可能包含了多个答案,
//所以别忘了需要对其逐个进行遍历。
for(let inside of dp[p]) {
for(let outside of dp[q]) {
dp[curN].push("(" + inside + ")" + outside);
}
}
}
}
/* 返回所求结果 */
return dp[n];
}
写在文末
我是来自在校学生编程兴趣小组江南游戏开发社的PAK向日葵,我们目前正在致力于开发自研的非营利性网页端同人游戏《植物大战僵尸:旅行》,以锻炼我们的前端应用开发能力。
我们诚挚邀请您体验我们的这款优秀作品,如果您喜欢TA的话,欢迎向您的同事和朋友推荐。如果您有技术方面的问题希望与我们探讨,欢迎直接与我联系。您的支持是我们最大的动力!
今天的文章【LeetCode选讲·第十一期】「括号生成」(DFS搜索,DP动态规划)分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/21520.html