代码随想录算法训练营第二十一天 | leetcode：组合总和III,电话号码的字母组合
0 / 0 / 创建于 11个月前 /
_zzh 的个人博客
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);
}
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号