首页 / JAVASCRIPT / [LeetCode][JavaScript]Remove Invalid Parentheses

[LeetCode][JavaScript]Remove Invalid Parentheses

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode][JavaScript]Remove Invalid Parentheses，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1747字，纯文字阅读大概需要3分钟。

内容图文

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
https://leetcode.com/problems/remove-invalid-parentheses/
 
 
 
 
 
 
 
( 和 )总是成对出现的，出现在 ( 之前的 ) 没有意义。
开变量countLeft记录还没匹配的 ( 的次数。
 
每轮循环三种情况：
1. (， 可以选择拿或不拿;
2. )， 如果有没匹配的 ( ，可以选择拿或不拿，否则只能不拿;
3. 其他字母直接拿。
 
因为要移除最少的括号，开变量maxLeft记录最多有几对括号，即最多出现过几个匹配成功的 (。
注意到这两句话的顺序:

dfs(str.substring(1), subRes + ‘(‘, countLeft + 1, maxLeft + 1);
dfs(str.substring(1), subRes, countLeft, maxLeft);

保证了匹配括号多的结果一定会先出现在结果数组中，不会遗漏结果。

https://leetcode.com/discuss/68272/straight-forward-solution-with-explanation

 

                 1
                /*
                *

                 2
                 * @param {string} s

                 3
                 * @return {string[]}

                 4
                */
                 5
                var removeInvalidParentheses = function(s) {
 6var res = [], max = 0;
 7     dfs(s, "", 0, 0);
 8return res.length !== 0 ? res : [""];
 910function dfs(str, subRes, countLeft, maxLeft){
11if(str === ""){
12if(countLeft === 0 && subRes !== ""){
13if(maxLeft > max)
14                     max = maxLeft;
15if(max === maxLeft && res.indexOf(subRes) === -1)
16                    res.push(subRes);
17            }
18return;
19        }
20if(str[0] === ‘(‘){
21             dfs(str.substring(1), subRes + ‘(‘, countLeft + 1, maxLeft + 1);
22             dfs(str.substring(1), subRes, countLeft, maxLeft);
23         }elseif(str[0] === ‘)‘){
24if(countLeft > 0)
25                 dfs(str.substring(1), subRes + ‘)‘, countLeft - 1, maxLeft);
26             dfs(str.substring(1), subRes, countLeft, maxLeft);
27         }else{
28             dfs(str.substring(1), subRes + str[0], countLeft, maxLeft);
29        }
30    }
31 };

 

 
 

原文：http://www.cnblogs.com/Liok3187/p/4946376.html

内容总结

以上是互联网集市为您收集整理的[LeetCode][JavaScript]Remove Invalid Parentheses全部内容，希望文章能够帮你解决[LeetCode][JavaScript]Remove Invalid Parentheses所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1108435.html

来源：【匿名】