If the cover is good, you’ll get a thumbs up. ^ – ^

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

10. Letter combinations for the phone number (column -a-phone-number)

The label

  • DFS/BFS
  • back
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Gives telephone mapping from numbers to letters. Given a string containing only the numbers 2-9, return all the letter combinations it can represent. It’s a deep traversal problem.

Basic knowledge of

Let’s take a quick look at DFS/BFS and then the search algorithm will be refined, so let’s make an impression.

Deep First Search (DFS) Deep First Search.

The steps of depth-first search are divided into

  1. recursiveGo down
  2. backCome up to
  • As the name implies, depth first, the first road to the end, until the goal is reached. This is called going down recursively.
  • Otherwise, the goal has not been reached and there is no way to go, so it is back to the state of the previous step, take other road. So that’s going back.

Breath First Search (BFS) breadth-first Search.

Breadth-first search differs from depth-first search in that depth-first search aims to follow one path to the end, no matter how many forks there are, and then return to the previous intersection and choose the next fork.

The goal of breadth-first search is to write down all the forks at one intersection, select one to enter, record its branching, and then go back to the other fork and repeat the process

The two different

  1. The application of this data structure is understood in combination with the following code
  • DFS uses a recursive stack structure, first in, last out.
  • BFS selects state in the form of queue, first in, first out.
  1. The complexity of the

The complexity of DFS is roughly the same as that of BFS, but the difference is that the way of traversal is different from the starting point of solving the problem.

  • DFS is good for being goal-oriented
  • BFS is suitable for a wide range of searches
  1. thought

Ideologically, both of these methods are traversal and exhaustive.

The basic idea

  1. Create a mapping map that maps numeric => letter strings
  2. Use DFS to recursively iterate through the results

Writing implement

/ * * *@param {string} digits
 * @return {string[]}* /
const letterMap = {
  '2': 'abc'.'3': 'def'.'4': 'ghi'.'5': 'jkl'.'6': 'mno'.'7': 'pqrs'.'8': 'tuv'.'9': 'wxyz'
}

var letterCombinations = function(digits) {
  let res = []
  // DFS, the passed argument is the digits string,
  // index is the number of digits recursive to the string,
  // tempStr is a temporary substring used for concatenation
  let letterFun = (digits, index, tempStr) = > {
    // Recursive exit, when our index is already digits the length means we are at the last digit
    // So tempStr is one of the results, and we string it directly into the result array
    if (index === digits.length) {
      res.push(tempStr)
      return;
    }
    // We also use a temporary variable to make it clear what string of letters we are currently concatenating
    let letters = letterMap[digits[index]]
    for (letter of letters) {
      // The point is to recursively concatenate each letter after the substring to the next recursion
      letterFun(digits, index + 1, tempStr + letter)
    }
    return
  }
  // Void direct output []
  if (digits === "") {
      return[]}// Use DFS to recurse and back up
  letterFun(digits, 0.' ')
  return res
};

console.log(letterCombinations('23'))
Copy the code

And the other way, instead of recursively, you write it iteratively and functionally

var letterCombinations = function (digits) {
  // Use the array index as key to convert substrings to arrays
  const CHAR_MAP = [' '.' '.'abc'.'def'.'ghi'.'jkl'.'mno'.'pqrs'.'tuv'.'wxyz'].map((s) = > s.split(' '));
  return digits.length === 0 ? [] : 
    digits.split(' ')
    .map((d) = > CHAR_MAP[d])
    .reduce((acc, cur) = > acc.reduce(
        (iacc, parent) = > iacc.concat(
          cur.map((item) = > `${parent}${item}`)), [])// Note that this has an initial value, so cur starts at the first element
    ); // This has an initial value, so cur starts with the second element
};
Copy the code

Today is New Year’s eve, let’s have a question.

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me Presious tower shock the reiver monster, I see the pass, the code is not on

reference

  • Juejin. Cn/post / 690713…