This is the 16th day of my participation in Gwen Challenge

Topic describes

A combination of letters for a telephone number

Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order. The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter. Leetcode-cn.com/problems/le…

/ / sample 1Enter: digits ="23"Output:"ad"."ae"."af"."bd"."be"."bf"."cd"."ce"."cf"]
/ / sample 2Enter: digits ="2"Output:"a"."b"."c"]
Copy the code

The label

DFS back

Analysis of the problem solving

1. DFS back

Let’s get right to it.

The core is backtracking, when the search does not meet the results, back to the root node, start the next backtracking. But it's not reflected in this problem, so it's just a violent search. Assuming that the string is passed in'234'

2[a, b, c] :3:  [d,e,f]
4: [g,h, I] Direct violence search to0To start the recursion.string[0[A, B, C] => [B, C0Each number in is a node, and continue recursing through the string a => to the NTH +1AD, AE, AF, and then run to n+2Adg, ADH, ADI, AEG, AEH, AEI, AFG, AFH, AFI until finally, when all the data sets run out and there's no data left, return the array and exit the current recursion. Each node is equivalent to a recursive run!Copy the code

Go to ！！！！！

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']])// Empty string, pointer
   const dfs = (cur, i) = > {
       // There are no special conditions for this problem, you can exit after traversing the data set
       if(i > digits.length - 1) {
           result.push(cur)
           return
       }
       // Recurse with the data in each dataset
       const curNum = map.get(digits[i])
       for(let num of curNum) {
           dfs(cur + num, i+1)}}// start with 0 as the first dataset
   dfs(' '.0)
   return result
};


Copy the code

The last

Not pigeon from today, every day an algorithm problem and published articles, first want to solve the problem group for Top100, the eighth topic finished work!!