2020-04-24

leetcode 括号问题：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：

输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

以下是我的PHP代码，没通过，因为执行超时了。但是当括号数较少时能够拟合，记录下来以作备忘。

class Solution {

    /**
     * @param Integer $n
     * @return String[]
     */

    function generateParenthesis($n)
    {
        $site = "()";

        $res = $this->insertStr('', $site );
        for ($i = 1; $i < $n; $i++) {
            foreach ($res as $item) {
                $res = array_merge($res, $this->insertStr($site, $item));
            }
        }

        $ret = $this->filter($n, array_unique($res));


        return array_unique($ret);

    }


    function insertStr($site, $res) {
        $arr = [];
        for($i = 0; $i <= strlen($res); $i++) {
            $arr = array_merge($arr, [substr_replace($res, $site, $i, 0)]);
        }

        return $arr;
    }

    function filter($n, $arr) {
        $reArr = [];
        foreach ($arr as $item) {
            if (strlen($item) < $n*2) continue;
            $reArr[] = $item;
        }

        return $reArr;
    }
}

(new Solution())->generateParenthesis(4);