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

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循环和纵向递归。

解题方法

  1. 使用map做好数字与字母的映射
  2. 组合长度k 始终等于输入digits的长度
  3. 根据图示不难看出,横向for循环为第一个数字指定的字母,纵向是第一个数字指定的字母依次与后续数字字母的组合。
    代码随想录算法训练营第二十一天 | leetcode:组合总和III,电话号码的字母组合

复杂度

时间复杂度

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);
        }
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!