17. 电话号码的字母组合

[Geekhyt]

原题链接

回溯法

使用回溯法进行求解，回溯是一种通过穷举所有可能情况来找到所有解的算法。

如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。

究其本质，其实就是枚举。

如果没有更多的数字需要被输入，说明当前的组合已经产生。

如果还有数字需要被输入：

• 遍历下一个数字所对应的所有映射的字母。
• 将当前的字母添加到组合最后，也就是 str + tmp[r] 。

const letterCombinations = function (digits) {
    if (!digits) {
        return []
    }
    const len = digits.length
    const map = new Map()
    map.set('2', 'abc')
    map.set('3', 'def')
    map.set('4', 'ghi')
    map.set('5', 'jkl')
    map.set('6', 'mno')
    map.set('7', 'pqrs')
    map.set('8', 'tuv')
    map.set('9', 'wxyz')
    const result = []

    function generate(i, str) {
        if (i === len) {
            result.push(str)
            return
        }
        const tmp = map.get(digits[i])
        for (let r = 0; r < tmp.length; r++) {
            generate(i + 1, str + tmp[r])
        }
    }
    generate(0, '')
    return result
}

N+M是输入数字的总数

• 时间复杂度：O(3^N * 4^M)
• 空间复杂度：O(3^N * 4^M)