This is the 17th day of my participation in the August Text Challenge.More challenges in August

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: digits = “23”

Output: [” AD “, “ae”, “af”, “bd”, “be”, “bf”, “CD” and “ce”, “cf”]

Example 2:

Enter: digits = “”

Output: []

Example 3:

Input: digits = “2”

Output: [” a “, “b”, “c”]

 

Tip:

  • 0 <= digits.length <= 4
  • digits[i]Is the scope of[' 2 ', '9']A number of.

Their thinking

Idea 1

It’s a matter of “translating” a string of numbers into a string of letters to find out all the translation possibilities. There are 3/4 options for translating the first number and 3/4 options for translating the second number… From the first translation to the last, it expands into a recursive tree. The pointer I is the index of the character being examined. When the pointer goes out of bounds, it generates a solution, adds the solution set, ends the recursion, goes to another branch, finds all the solutions.

Time complexity: Traverse all nodes, worst case to O(4n)O(4^n)O(4n), NNN is the length of the number string. Spatial complexity: O(n)O(n)O(n), depth of recursive stack calls.

code

const letterCombinations = (digits) = > {
  if (digits.length == 0) return [];
  const res = [];
  const map = { '2': 'abc'.'3': 'def'.'4': 'ghi'.'5': 'jkl'.'6': 'mno'.'7': 'pqrs'.'8': 'tuv'.'9': 'wxyz' };
  // DFS: the string currently constructed is curStr, now "translate" to the i-th digit, and continue "translate" from there.
  const dfs = (curStr, i) = > {   // curStr is the current string, and I is the scanned pointer
    if (i > digits.length - 1) { // Pointer out of bounds, recursive exit
      res.push(curStr);          // Push the solution into res
      return;                    // End the current recursive branch
    }
    const letters = map[digits[i]]; // The letter corresponding to the current number
    for (const letter of letters) { // A letter is a selection, corresponding to a recursive branch
      dfs(curStr + letter, i + 1);  // Select letter to generate a new string, move I pointer right to continue translation (recursive)}}; dfs(' '.0); // A recursive entry, starting with string '', translated from subscript 0
  return res;
};
Copy the code

Backtracking as I understand it

Backtracking is a violent search in nature. In the solution space tree of the problem, DFS is used to search the whole solution space starting from the root node. If you want to find all of the solutions, you search the entire subtree. If you find only one solution, you end the search by finding one solution.

“Find all possible combinations” problem, suitable for backtracking algorithm.

The backtracking algorithm has three main points:

  1. Selection determines which branches you have at each node, helping you build a spatial tree of solutions. The choice in this case is, you have multiple letters for each number, and if you choose one of those letters, you keep recursing
  2. Constraints are used for pruning, pruning subtrees that do not meet the constraints to avoid invalid searches. I don’t think I did that very well, right
  3. The goal determines when to capture the solution, or cut the subtree that can’t find the solution, backtracking ahead. We can add the solution to the solution set when we run out of Pointers to scan numbers.

Idea 2: BFS solution

Maintain a queue. You start with an empty string in the column, and you get the strings in the current layer out of the column, and the string that’s out of the column is going to build a new string of the next layer and merge it into the column. So layer by layer, you get to the bottom of the string, you get to the bottom of the string, and that’s where all the strings are, and you go back to the queue.

This controls the depth of the sequence traversal, which is the length of digits instead of while(queue.length){… } if all the nodes are in and out of the queue, there will still be one last layer of nodes left in the queue.

BFS code

const letterCombinations = (digits) = > {
  if (digits.length == 0) return [];
  const map = { '2': 'abc'.'3': 'def'.'4': 'ghi'.'5': 'jkl'.'6': 'mno'.'7': 'pqrs'.'8': 'tuv'.'9': 'wxyz' };

  const queue = [];
  queue.push(' ');
  for (let i = 0; i < digits.length; i++) { // The number of BFS layers, that is, the length of digits
    const levelSize = queue.length;         // The number of nodes in the current layer
    for (let j = 0; j < levelSize; j++) {   // List the nodes of the current layer one by one
      const curStr = queue.shift();         / / dequeue

      const letters = map[digits[i]];       

      for (const l of letters) {
        queue.push(curStr + l); // Generate a new string of letters into the column}}}return queue; // The queue is full of strings generated by the last layer
};
Copy the code

Idea 3

After understanding this problem, you need to solve the following three problems:

  1. How do numbers and letters map
  2. Two letters for two for loops, three characters for three for loops, and so on, and then you can’t write the code
  3. Enter the 1 * # key and other exceptions

How do numbers and letters map

The mapping can be done using a map or by defining a two-digit array such as String letterMap[10].

const string letterMap[10] = {
    ""./ / 0
    ""./ / 1
    "abc"./ / 2
    "def"./ / 3
    "ghi"./ / 4
    "jkl"./ / 5
    "mno"./ / 6
    "pqrs"./ / 7
    "tuv"./ / 8
    "wxyz"./ / 9
};
Copy the code

Backtracking to solve n for loops

For example, input: “23”, which is abstracted into a tree structure, as shown in the figure:

Can be seen in the graph traversal depth is the length of the input “23”, and the leaf node is what we want to collect as a result, the output (” AD “, “ae”, “af”, “bd”, “be”, “bf”, “CD” and “ce”, “cf”].

Back to trilogy:

  • Determine the traceback function parameters

I first need a string S to collect the results of the leaf node, and then store them in an array of strings called result. I still define these two variables as global.

And the parameter, the parameter is the string digits given in the problem, and then the parameter is the index of type int.

The index is the number of digits to iterate through, and the index is the depth of the tree.

  • Determine termination conditions

For example, enter the use case “23”, two numbers, and the root node recurses two levels down, while the leaf node is the result set to collect.

The termination condition is if index is equal to the number of digits entered (digits.size) (index is used to iterate over digits).

The results are then collected to end this layer of recursion.

  • Determine the single-layer traversal logic

The first step is to take the number index points to and find the corresponding character set (the character set of the mobile phone keyboard).

The for loop then processes the character set

code

var letterCombinations = function(digits) {
    const k = digits.length;
    const map = ["".""."abc"."def"."ghi"."jkl"."mno"."pqrs"."tuv"."wxyz"];
    if(! k)return [];
    if(k === 1) return map[digits].split("");

    const res = [], path = [];
    backtracking(digits, k, 0);
    return res;

    function backtracking(n, k, a) {
        if(path.length === k) {
            res.push(path.join(""));
            return;
        }
        for(const v of map[n[a]]) {
            path.push(v);
            backtracking(n, k, a + 1); path.pop(); }}};Copy the code

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way

“Front brush” No.17