leetcode top100挑战, 每天不鸽一道题之电话号码的字母组合(8/100)-一一网

这是我参与更文挑战的第16天，活动详情查看：更文挑战

题目描述

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

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

leetcode-cn.com/problems/le…

// 示例1 
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 示例2 
输入：digits = "2"
输出：["a","b","c"]
复制代码

解题分析

1. DFS回溯

直接上讲解。

核心就是回溯，当搜索中达不到符合的结果时，就回溯回根节点，开始下一个回溯。

不过在这题中没有体现，直接暴力搜索就行。

假设传入的字符串时 '234'

2： [a,b,c]
3:  [d,e,f]
4:  [g,h,i]
直接暴力搜索 
以0为起始，开始遍历递归。

string[0] => [a,b,c]

然后以0中的每个数字为节点，继续递归整个字符串

a => 跑到第n+1个数据中遍历， ad, ae, af, 再跑到n+2个数据中， 
adg, adh, adi, 
aeg, aeh, aei,
afg, afh, afi

直到最后，当所有数据集跑完，没有数据了再返回数组并退出当前递归。

每一个节点相当于一个递归跑起来！
复制代码

来人上代码！！！！！

function letterCombinations(digits: string): string[] {
    if(digits.length === 0) return []
    
    const result: string[] = []
    const map = new Map([
        ['2', 'abc'],
        ['3', 'def'],
        ['4', 'ghi'],
        ['5', 'jkl'],
        ['6', 'mno'],
        ['7', 'pqrs'],
        ['8', 'tuv'],
        ['9', 'wxyz'],
    ])
   // 空字符串，指针
   const dfs = (cur, i) => {
       //这题没有特殊条件，当遍历完数据集就可以退出了
       if(i > digits.length - 1) {
           result.push(cur)
           return
       }
       // 以每个数据集中的数据来进行递归
       const curNum = map.get(digits[i])
       for(let num of curNum) {
           dfs(cur + num, i+1)
       }
   }
   // 以0 第一个数据集为起点
   dfs('', 0)
   return result
};


复制代码