腾讯&leetcode22：括号生成 #112

Activity

1. sisterAn

   added

   腾讯

   LeetCode

   on Sep 23, 2020
2. oxyzhg commented on Sep 24, 2020

   

   oxyzhg

   on Sep 24, 2020

   More actions

   /**
    * @param {number} n
    * @return {string[]}
    */
   var generateParenthesis = function(n) {
     let str = "";
   
     const addBrackets = target => {
       if (target.length === n * 2) return [target]; // 递归结束条件
   
       let result = [];
   
       let matchedStart = target.match(/\(/g);
       let matchedEnd = target.match(/\)/g);
       let matchedStartCount = matchedStart ? matchedStart.length : 0; // 左边已经出现的 `(` 个数
       let matchedEndCount = matchedEnd ? matchedEnd.length : 0;
   
       /**
        * 下一位字符一定是开始括号的几种情况：
        * 1. 空字符串
        * 2. 开始括号数量等于闭合括号数量
        */
       if (target.length === 0 || matchedStartCount === matchedEndCount) {
         return [...result, ...addBrackets(target + "(")];
       }
   
       if (target.length === n * 2 - 1 || matchedStartCount === n) {
         return addBrackets(target + ")");
       }
   
       /**
        * 左边已出现的开始括号个数
        * 1. 如果小于n，表明未来还可新增新的成对括号
        * 2. 如果大于等于n，表明未来不会再新增成对括号
        */
       if (matchedStartCount < n) {
         result = [...result, ...addBrackets(target + "(")];
       }
   
       result = [...result, ...addBrackets(target + ")")];
   
       return result;
     };
   
     return addBrackets(str);
   };

   尝试解题失败，这写法执行时间和消耗内存挺高。记录下过程，等看看大家有什么好的解题思路。
3. dinjufen commented on Sep 24, 2020

   

   dinjufen

   on Sep 24, 2020

   More actions

   /**
    * @param {number} n
    * @return {string[]}
    */
   var generateParenthesis = function(n) {
       let res = [];
       let path = [];
       traverse(n, n, path);
       function traverse(left, right, path) {
           if (left < 0 || right < 0) {
               return;
           }
           if (right < left) {
               return;
           }
           if (left === 0 && right === 0) {
               res.push(path.join(''));
               return;
           }
           path.push('(');
           traverse(left-1, right, path);
           path.pop();
   
           path.push(')');
           traverse(left, right-1, path);
           path.pop();
       }
       return res;
   };
4. huangruoliang commented on Sep 24, 2020

   

   huangruoliang

   on Sep 24, 2020

   More actions

       let res = []
       const back = (path,left,right) => {
           if(path.length === n *2 ) {
               res.push(path)
               return 
           }
           if(left > 0) {
               back(path+ '(',left-1,right)
           }
           if(right > left) {
               back(path+ ')',left,right-1)
           }
       }
       back('',n,n)
       return res
   };
   

   👍React with 👍1Reacted by hyyabc123

   🎉React with 🎉1Reacted by Jet

   🚀React with 🚀1Reacted by Jet
5. sisterAn commented on Sep 24, 2020

   

   sisterAn

   on Sep 24, 2020

   OwnerAuthor

   More actions

   解答：回溯算法（深度优先遍历）

   算法策略： 回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

   对应于本题，我们可以每次试探增加 ( 或 ) ，注意：

   • 加入 ( 的条件是，当前是否还有 ( 可以选择

   • 加入 ) 的时候，受到 ( 的限制，如果已选择的结果里的 ( 小于等于已选择里的 ) 时，此时是不能选择 ) 的，例如如果当前是 () ，继续选择 ) 就是 ()) ，是不合法的

   代码实现：

   const generateParenthesis = (n) => {
       const res = []
       const dfs = (path, left, right) => {
           // 肯定不合法，提前结束
           if (left > n || left < right) return
           // 到达结束条件
           if (left + right === 2 * n) {
               res.push(path)
               return
           }
           // 选择
           dfs(path + '(', left + 1, right)
           dfs(path + ')', left, right + 1)
       }
       dfs('', 0, 0)
       return res
   }

   复杂度分析（来源leetcode官方题解）：

   

   leetcode

   👍React with 👍5Reacted by Kyle, 虾虾郑, hyyabc123, iceberg211 and leogogo