17. 电话号码的字母组合

题意：

解题思路：

思路：
    1. 通过key找到对应的字母；
    2. 递归拼接新字母；
    3. 递归到目标长度，将当前字符串加入到数组中；

PHP代码实现：

class Solution {
    public $res = [];
    public $str = "";
    public $array = [
        "2" => ["a","b","c"],
        "3" => ["d","e","f"],
        "4" => ["g","h","i"],
        "5" => ["j","k","l"],
        "6" => ["m","n","o"],
        "7" => ["p","q","r","s"],
        "8" => ["t","u","v"],
        "9" => ["w","x","y","z"],
    ]; 
    function letterCombinations($digits) {
        if (!$digits) return [];
        return $this->queue($digits, $step);
        $this->dfs($digits, 0);
        return $this->res;
    }
    function dfs($digits, $step) {
        if ($step == strlen($digits)) {
            $this->res[] = $this->str;
            return;
        }
        $key = substr($digits, $step, 1);
        $chars = $this->array[$key];
        foreach ($chars as $v) {
            $this->str .= $v;
            $this->dfs($digits, $step + 1);
            $this->str = substr($this->str, 0, strlen($this->str) - 1);
        }
    }
    function queue($digits, $step) {
        if (empty($digits))  return [];
        // 先创建字典
        $dic = ["0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];
        // 创建一个用于模拟队列的数组
        $resultList = [''];
        // 循环输入$digits
        for ($i = 0; $i < strlen($digits); $i++) {
            // 先获取当前$i对应的输入的字符串
            // 再使用intval 转成整形，用于根据键值对取对应的字符串
            $mapIndex = intval($digits[$i]);
            // 总是判断当前$resultList的第一个元素的字符长度是否等于当前$i
            while (strlen($resultList[0]) == $i) {
                // 将数组$resultList开头的单元移出数组
                $head = array_shift($resultList);
                $str = $dic[$mapIndex];
                for ($j = 0; $j < strlen($str); $j++) {
                    $resultList[] = $head. $str[$j];
                }
            }
        }
        return $resultList;
    }
}

GO代码实现：

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    list := make([]byte, 0)
    result := make([]string, 0)
    backtrack(digits, 0, list, &result)
    return result
}
var table = map[byte][] byte {
    '2': []byte(`abc`),
    '3': []byte(`def`),
    '4': []byte(`ghi`),
    '5': []byte(`jkl`),
    '6': []byte(`mno`),
    '7': []byte(`pqrs`),
    '8': []byte(`tuv`),
    '9': []byte(`wxyz`),
}
func backtrack(s string, idx int, list []byte, result *[]string) {
    if idx == len(s) {
        *result = append(*result, string(list))
        return 
    }
    c := table[s[idx]]
    for i := 0; i < len(c); i++ {
        list = append(list, c[i])
        backtrack(s, idx + 1, list, result)
        list = list[:len(list) - 1]
    }
}