【PHP解法==LeetCode（回溯递归1）】17.电话号码的字母组合 && 93. 复原IP地址 && 131. 分割回文串
目录
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
分析：如下图，digits = “23”。此时2可以表示为abc，3可以表示为def，则依次相连
解法：递归解法
class Solution {
//数字->字符：映射数组
private $letterMap = [
'', //0
'', //1
'abc', //2
'def', //3
'ghi', //4
'jkl', //5
'mno', //6
'pqrs', //7
'tuv', //8
'wxyz' //9
];
/**
* @param String $digits
* @return String[]
*/
function letterCombinations($digits) {
$res = []; //初始化结果数组
$len = strlen($digits); //初始化判断，若长度为0，则返回空数组
if($len == 0) return $res;
$this->findCombination($digits,$len,0,'',$res); //进行递归回溯操作
return $res;
}
/**
* [递归回溯寻找最终结果值]
* @param [type] $digits [$digits]
* @param [type] $len [$digits数组的长度]
* @param [type] $index [下标]
* @param [type] $str [每一次的连接结果]
* @param [type] &$res [结果数组]
*/
private function findCombination($digits,$len,$index,$str,&$res){
if($index == $len){ //当下标==数组长度时，已经找到了最终结果，记录并返回
$res[] = $str;
return ;
}
$letters = $this->letterMap[$digits[$index]]; //找到对应下标数字可以转换的对应字母
$lens = strlen($letters);
for($i = 0;$i<$lens;++$i){
$this->findCombination($digits,$len,$index+1,$str.$letters[$i],$res); //连接上其中一个字母，下标+1，进行下一次循环
}
return ;
}
}93. 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135" 输出:["255.255.11.135", "255.255.111.35"]
解法：递归回溯，终止条件为ip已经分到第四部分/下标已经到达字符串长度
注意：（1）0开头的字符，只能单独做ip的一个部分
（2）已经是3个数字的，数字的大小不能超过255
（3）递归时最后一个部分不用连接“.”
（4）递归参数（下标，暂存的结果，已经分到第几部分）
class Solution {
private $res = []; //初始化结果数组
private $s,$len; //记录s和s的长度
/**
* @param String $s
* @return String[]
*/
function restoreIpAddresses($s) {
$this->len = strlen($s);
$this->s = $s;
if($this->len > 12 || $this->len < 4) return $this->res //初始化条件判断，ip的数字不能大于12也不能小于4
$this->findIp(0,'',0); //进行递归遍历
return $this->res;
}
/**
* [递归回溯寻找正确的IP]
* @param [type] $index [下标]
* @param [type] $path [暂存的结果路径]
* @param [type] $part [ip记录到第几部分，一个IP有4个部分]
*/
private function findIp($index,$path,$part){
//当ip记录到了第4部分并且下标长度到达$s的长度，即无法继续进行下去，记录结果数组并返回
if($index == $this->len && $part == 4){
$this->res[] = $path;
return;
}
if($part == 4) return; //当$part到达第四部分时，无法再继续进行下去，直接返回
$connect = $part == 3 ? '':'.'; //当$part到达3，即最后一个部分时，就不再需要连接小数点“.”
if($this->s[$index] == '0'){ //当s在该下标下的字符是0时，则直接进行下一循环，0只能单独占一个部分
$this->findIp($index+1,$path.'0'.$connect,$part+1);
}else{
$num = ''; //继续进行循环，连接往后的3个数字，且不能超过$s的长度
for($i = $index;$i<$index+3 && $i<$this->len;++$i){
$num .= $this->s[$i];
if((int)$num > 255) return; //当数字超过255时，直接返回，ip不可能超过255
$this->findIp($i+1,$path.$num.$connect,$part+1);//进行下次递归回溯
}
}
}
}131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
解法：递归回溯，终止条件为下标已经到达字符串长度
注意：（1）只有当字符串是回文的时候，压入暂存的结果数组，再进行递归
（2）完成递归后，要弹出暂存的结果数组，完成回溯操作，才能压入新的元素
（3）该题会从头遍历到尾，从1个字符往后慢慢增加
class Solution {
private $res = []; //初始化结果数组
private $s,$len; //初始化$s和$s的长度
/**
* @param String $s
* @return String[][]
*/
function partition($s) {
$this->len = strlen($s);
$this->s = $s;
if($this->len == 0) return $this->res; //初始化判断：当字符串为空时，不存在回文字符串，直接返回空数组
$this->findPartition(0,[]); //进行递归回溯
return $this->res;
}
/**
* [递归回溯寻找合适的回文数组]
* @param [type] $index [下标]
* @param [type] $path [暂存满足条件的回文数组]
*/
private function findPartition($index,$path){
if($index == $this->len){ //当下标==字符串长度时，无法继续进行下去，记录结果数组并返回
$this->res[] = $path;
return;
}
$str = ''; //记录可能的回文字符串
for($i=$index;$i<$this->len;++$i){ //尝试每一种可能
$str .= $this->s[$i]; //连接字符串
if($this->isHuiWen($str)){ //判断该字符串是否是回文字符串
$path[] = $str; //是，则保存路径，并继续递归
$this->findPartition($i+1,$path); //下标+1，传递残存的路径
array_pop($path); //回溯：弹出路径，下一次可以插入新的值
}
}
}
/**
* [判断字符串是否是回文]
* @param [type] $s [传入的字符串]
*/
private function isHuiWen($s){
//从前往后和从后往前都是一样的字符
for($i = 0,$j = strlen($s)-1;$i<$j;++$i,--$j){
if($s[$i] != $s[$j])
return false;
}
return true;
}
}