Leetcode基础刷题之PHP解析(22. Generate Parentheses)
2019-6-4 星期二 开始吧
上一题链接Leetcode基础刷题之PHP解析(17. Letter Combinations of a Phone Number)
这周选了leetcode递归的标签，这两天刷的都是递归的题目，其实我很害怕递归，我记得一开始做递归的时候老把自己绕进去，千万千万不要一层层的想进去，这个工作只有计算机能做，你要想的只是递归的出口，当前层的计算以及当前层和下一层之间的关系。
题目描述
给定一个数字，让我们组合所有()的情况，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
No Comments