This is the 23rd day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Early next month algorithm series, writing ideas have been:

Sliding window => BFS, DFS => backtracking method, each classic!

  • Sliding Window
  • “Spicy Sky! Sliding Window of [sum Max] & [Maximum Set]”
  • Keep Moving! Sliding Window median and Sliding Rubik’s Cube
  • Ok, BFS, again!
  • Okay, DFS, Too!
  • From DFS to Backtracking: The N Queen Problem

This article will continue with the backtracking method!

Classic title: the alphabet of telephone numbers

Topic:

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"] example 2: input: who = "" output: [] example 3: input: ["a","b","c"]Copy the code

Answer:

  1. Use map to store letters corresponding to numbers
  2. Start with the first number, take a letter, then from the second number, take a letter, the third number, take a letter…
  3. After iterating through the numbers, add the concatenated string STR to the result array RES
  4. Backtrace, modify the letter corresponding to the last number
  5. Repeat process 2-4

JS:

Var lettershape = function (digits) {return string (digits. Length === 0) return []; let numMap = new Map([ ['0', ''], ['1', ''], ['2', 'abc'], ['3', 'def'], ['4', 'ghi'], ['5', 'jkl'], ['6', 'mno'], ['7', 'pqrs'], ['8', 'tuv'], ['9', 'wxyz'] ]) let res = []; dfs("", digits); return res; Function DFS (STR, digit) {// If the string is empty, add the concatenated characters to the array if (digital.length === 0) res.push(STR); Else {// Digit nummap.get (digit[0]); For (let I = 0; i < numstr.length; i++) { str += numstr[i]; DFS (STR, digital.slice (1)) // Backtrace STR = str.slice(0, -1); }}}};Copy the code

Summary: 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.

OK, the above is the share ~ writing is not easy, like encourage 👍👍👍

I am Anthony Nuggets, the public account of the same name, every day a pawn, dig a gold, goodbye ~