电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

电话

示例

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

思路

全排列

  • 将 数字跟字母 建立映射关系 {2: 'abc'},

  • 数字的长度，就是遍历的深度，递归时，深度减一，当深度为0的时候，停止递归，返回结果，当深度为1的时候，添加到结果

  • 当需要继续递归的时候，保留之前的结果，此结果为了下一次遍历字母的时候，为每一个结果都要添加新的字符

  • 以 "23" 为例子， 转换字母 array = ['abc', 'def']

  • prefix = [], result = [], 我们循环 array, 每次抽出 array[0], 对array[0]进行遍历

    • 当 prefix 里面没东西的时候，我们直接将 array[0]的值丢进去， 此时 prefix = ['a', 'b', 'c'], 进入下一次递归

  • 继续上面的操作， 此时我们的 array = ['def'], 抽array[0], 对他进行遍历，prefix = ['a', 'b', 'c'], result = [], dept = 1

    • 现在要对 def 遍历，跟 prefix 组合成 ['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf'], 此时dept = 1 可以将结果放到 result了，继续递归

  • 此时dept = 0 退出递归

代码

var letterCombinations = function(digits) {
    let length = digits.length;
    let result = [];
    let string = [];
    let map = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }

    for(let i = 0; i < length; i++) {
        string.push(map[digits[i]])
    }
    contribute(result, string, [], length);

    return result;
};

var contribute = function(result, array, prefix, dept) {
    if(dept == 0) {
        return prefix
    }
    let current = array[0];
    let temp = []
    let prefixLength = prefix.length;
    // current = "def"; prefix = [a, b, c]
    for(let i = 0; i < current.length; i++) {
        if(prefixLength == 0) {
            temp.push(current[i]);
            if(dept == 1) {
                result.push(current[i]);
            }
            continue;    
        }

        for(let j = 0; j < prefixLength; j++) {
            let s = prefix[j] + current[i];
            temp.push(s);
            if(dept == 1) {
                result.push(s);
            }
        }       
    }
    contribute(result, array.slice(1), temp, --dept)

}