代码随想录算法训练营第二十一天 | leetcode：组合总和III,电话号码的字母组合

_zzh 的个人博客 / 45 / 0 / 创建于 2个月前 / 更新于 2个月前

216. 组合总和 III

注意的地方

与昨天的《77. 组合》问题不同，不能包含相同的组合两次，这题需要注意去重。

解题方法

题目固定的数字范围为1-9，在《77. 组合》即解题基础上，需要处理path的累加比较，加入目标数组res时，当前path是否存在res中。

复杂度

时间复杂度

O(n * 2^n)

空间复杂度

O(n)

code

class Solution {

    private $res = [];
    private $path = [];
    private $max = 9;
    /**
     * @param Integer $k
     * @param Integer $n
     * @return Integer[][]
     */
    function combinationSum3($k, $n) {
        $this->backtracking($k, $n, 1);
        return $this->res;
    }

    function backtracking($k, $n, $starIndex){
        //print_r($this->path);
        //判断元素个数是否==k && 数组相加==n && 是否存在结果数组
        if(count($this->path) == $k && array_sum($this->path) == $n && !in_array($this->path, $this->res)){
            //先排序，然后放进结果数组，方便后面查重
            sort($this->path);
            $this->res[] = $this->path;
        }
        for($i = $starIndex; $i <= $this->max; $i++){
            $this->path[] = $i;
            $this->backtracking($k, $n, $i+1);
            array_pop($this->path);
        }
    }
}

17. 电话号码的字母组合

注意的地方

与之前的组合问题《77. 组合》《216. 组合总和III》不同，之前的回溯算法求组合都是一个集合里面求组合，这道题是两个集合里面求集合。单靠想象有点难理解，此时一定要画图，有助于理解什么是外层横向for循环和纵向递归。

解题方法

使用map做好数字与字母的映射
组合长度k 始终等于输入digits的长度
根据图示不难看出，横向for循环为第一个数字指定的字母，纵向是第一个数字指定的字母依次与后续数字字母的组合。

复杂度

时间复杂度

O(3^m * 4^n)
其中 m 是对应四个字母的数字个数，n 是对应三个字母的数字个数

空间复杂度

O(3^m * 4^n)

code

class Solution {
    private $relate = [
        '','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'
    ];
    private $res = [];
    private $path = [];

    /**
     * @param String $digits
     * @return String[]
     */
    function letterCombinations($digits) {
        if(strlen($digits) == 0) return $this->res;
        $this->backtracking($digits,0);
        return $this->res;
    }
    //index 是digits的下标
    function backtracking($digits,$index){
        //当index = strlen($digits)时 代表遍历完了
        if($index == strlen($digits)){
            $this->res[] = implode("",$this->path);
            return;
        }
        $number = $digits[$index];
        $letter = $this->relate[$number];
        for($i = 0; $i < strlen($letter); $i++){
            $this->path[] = $letter[$i];
            $this->backtracking($digits, $index+1);
            array_pop($this->path);
        }
    }
}