“This is the 28th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

17. Alphabetic combinations of telephone numbers

The title

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.

Example 1

Input: who = "23" output: [" AD ", "ae", "af", "bd", "be", "bf", "CD" and "ce", "cf"]Copy the code

Example 2

["a","b","c"]Copy the code

Answer key

Full permutation idea: recursion + backtracking

The first thing to do is to convert the argument to a string; To build a hash table will be number one to one correspondence relation with letters: map = {2: ABC, 3: def, 4: ghi, 5: JKL, 6: mno, 7: PQRS, 8: tuv, 9: wxyz,} map = \ {2: ABC, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, \}map={2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz,}

Get one – to – one correspondence between numbers and letters

List =[ABC,def]list=[ABC,def]list=[ABC,def]list=[ABC,def]

Return all combinations of letters that it can represent.

According to the idea of full permutation, recursion + backtracking can definitely solve the problem

How do I recurse?

const len = list.length
// Start recursion
dfs(0[]);// idx: indicates the subscript in the list
function dfs(idx, path) {

    // The resulting string length must be equal to list, and this is also the termination condition for recursion
  if (path.length === len) {
    return;
  }
  for (let i = 0; i < (3||4); i++) {
      / / (| 3 | 4) : either 3 or 4, because the number seven PQRS said letters, there are four, so I may be less than 3 or less than 4, is dynamic;
      / / here to reflect the value of independence idx, independence idx said subscript in the list, I < (| 3 | 4); I < list[IDx].length}}Copy the code

How to backtrack?

for (let i = 0; i < list[idx].length; i++) {
      const s = list[idx][i];
      // Qualifying letters are added to the path and saved
      path.push(s);
      // Recursive next step
      dfs(idx + 1, path);
      // Backtrace, delete at the end of recursion
      path.pop();
      
  }
Copy the code

Why use arrays to store letters in paths? Because it’s easier to backtrack with arrays than strings

Edit the code as follows:

The complete code

const map = {
  2: 'abc'.3: 'def'.4: 'ghi'.5: 'jkl'.6: 'mno'.7: 'pqrs'.8: 'tuv'.9: 'wxyz'};var letterCombinations = function (digits) {
  const len = digits.length;
  if (len === 0) return [];
  const list = [];
  for (let i = 0; i < len; i++) {
    const k = digits[i];
    list.push(map[k]);
  }
  const result = [];
  dfs(0[]);return result;
  function dfs(idx, path) {
    if (path.length === len) {
      const t = path.join(' ');
      result.push(t);
      return;
    }

    for (let i = 0; i < list[idx].length; i++) {
      const s = list[idx][i];
      path.push(s);
      dfs(idx + 1, path); path.pop(); }}};Copy the code