Leetcode基础刷题之PHP解析(22. Generate Parentheses)


2019-6-4 期二 


Leetcode基础刷题之PHP解析(17. Letter Combinations of a Phone Number)


这周选了leetcode递归的标签,这两天刷的都是递归的题目,其实我很害怕递归,我记得一开始做递归的时候老把自己绕进去,千万千万不要一层层的想进去,这个工作只有计算机能做,你要想的只是递归的出口,当前层的计算以及当前层和下一层之间的关系。

860eacf62047b25e59ba5466837d272d.png

给定一个数字,让我们组合所有()的情况,1就代表一对(),每上一个数就代表就有几对括号。规则是括号一定要匹配。


每一次可以有两种选择加左括号还是加右括号,但是我们需要注意一个重要规则,如果当前右括号的数等于左括号出现的数,那么不能继续再加右括号了,否则肯定没有与他对应的左括号,递归出口呢?也就是左括号和右括号都用完的时候。

      /**
     * @param Integer $n
     * @return String[]
     */
    function generateParenthesis($n) {
        $res=[];
       $this->helper($res,"",$n,$n);
        return $res;
    }
    
    function helper(&$res,$cur,$open,$close){
        if($open == 0 && $close ==0) array_push($res,$cur);
        if($open>$close) return ;
         if($open>0) $this->helper($res,$cur.'(',$open-1,$close);
         if($close>0) $this->helper($res,$cur.')',$open,$close-1);
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D79 448. Find All Numbers Disappeared in an Array

>> 下一篇: Leetcode PHP题解--D80 182. Duplicate Emails