This is the 18th day of my participation in the More text Challenge. For more details, see more text Challenge

Letter combinations for telephone numbers (Question Number 17)

The title

Given a string containing only the numbers 2-9, return all the combinations of letters it can represent. The answers can be returned in any order.

Give the mapping of numbers to letters as follows (same as telephone keys). 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:

Input: digits = ""Copy the code

Example 3:

Input: digits = "2" Output: ["a","b","c"]Copy the code

Tip:

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

link

Leetcode-cn.com/problems/le…

explain

This problem, this problem is very complicated.

I feel like I’m forcing an easier way out of nothing. In fact, the first solution is enough. Because I’m not confident, I’m forcing another solution, and the result is meaningless and less efficient.

The solution to this problem is actually very simple, first make an object, record the letters corresponding to the numbers.

Then we start the cycle and we’re done. There’s nothing hard about it.

Specifically put in the code, the author came up with another approach is more complex, feel not very easy to understand.

Your own answer (three-level cycle)

First look at the code 👇 :

var letterCombinations = function(digits) { var obj = { 2: ['a', 'b', 'c'], 3: ['d', 'e', 'f'], 4: ['g', 'h' ,'i'], 5: ['j', 'k', 'l'], 6: ['m', 'n', 'o'], 7: ['p', 'q', 'r', 's'], 8: ['t', 'u', 'v'], 9: ['w', 'x', 'y', 'z'] } arr = [] for (const num of digits) { if (! arr.length) { arr = obj[num] } else { var tmp = [] for (const item of obj[num]) { for (const item2 of arr) { tmp.push(`${item2}${item}`) } } arr = tmp } } return arr };Copy the code

In addition to the object, there is only one extra variable declared here, called arr, which is actually the final result, or res.

After res is empty, we start to loop through each element in digits. Inside the loop, we first determine if arr is empty. If it is, we put in the array of letters corresponding to obj.

And then we’re going to loop through the second and third levels, and we’re going to loop through the array of letters that the current element represents, and we’re going to loop through the arR, and we don’t care what order we’re going to loop through, because we’re going to exhaust all the possibilities.

In the innermost loop, you can concatenate strings. Update the ARR array.

If you still don’t understand, here is 🌰 -> 234.

Start the outermost loop first. Arr is null, so assign arr directly. After the loop, arr is:

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

Then start the second loop, matching arR with the letter represented by the number 3. The number of results is 3 * 3, which is 👇 :

[' AD ', 'bd', 'CD' to 'ae', 'be', 'ce' and 'af', 'bf', 'cf']Copy the code

Then start the third layer of the loop, matching arR with the letter represented by the number 4. The number of results is 9 * 3, which is 👇 :

[' adg ', 'BDG', 'the CDG', 'aeg', 'beg', 'ceg', 'afg', 'BFG', 'access', 'adh', 'BDH', 'CDH', 'aeh', '; ' 'ceh', 'afh', 'BFH', 'CFH', 'adi', 'bdi', 'cdi', 'aei', 'bei', 'the cei', 'as' and' bfi ', 'cfi]Copy the code

So we can get the final result, the whole idea is relatively simple.

Your own answers (carry)

This method is a bit of a strange idea, really do not know how they think of.

First of all, assuming that the starting string represents the letter 000, the final possibility is 333 with 234 as 🌰, which translates to adG and cfI.

So let’s say the start variable is all the possibilities, and it goes from 000 all the way up to 333.

Let’s look at the array of letters 234 represents, which should be 👇 :

[
	['a', 'b', 'c'],
	['d', 'e', 'f'],
	['g', 'h' ,'i'],
]
Copy the code

The index of each element is adg, and the last one is cfi ‘.

So what you’re going to do is you’re going to keep updating the start array, and each time you update it, you’re going to insert an element into the result.

Notice that when you update it, you need to carry it. For example, the current start is 002, and the next time you increase it, it will be 003, which is beyond the maximum size of the current bit, so you need to carry it, and when you’re done, it will be 010, and then you can continue.

Keep carrying, you can find all the possibilities, 👇 look at the code:

var letterCombinations = function(digits) { var obj = { 2: ['a', 'b', 'c'], 3: ['d', 'e', 'f'], 4: ['g', 'h' ,'i'], 5: ['j', 'k', 'l'], 6: ['m', 'n', 'o'], 7: ['p', 'q', 'r', 's'], 8: ['t', 'u', 'v'], 9: ['w', 'x', 'y', 'z'] } res = [] len = digits.length item = new Array(len) max = new Array(len) start = new Array(len) transArr = new Array(len) for (let i = 0; i < digits.length; i++) { max[i] = obj[digits[i]].length - 1 start[i] = 0 transArr[i] = obj[digits[i]] } while (start.toString() ! == max.toString()) { for (let i = start.length - 1; i > -1; i--) { if (start[i] > max[i]) { start[i] = 0 start[i - 1] = start[i - 1] + 1 } } res.push(start.map((item, index) => transArr[index][item]).join('')) ++start[start.length - 1] } max.length && res.push(max.map((item, index) => transArr[index][item]).join('')) return res };Copy the code

This is the overall logic. Due to the condition of the while, we will miss the last condition, so we need to push the Max parsing into the Res array after the while is finished.

This method was supposed to be stronger, but it’s not, and it’s even more memory intensive because it stores multiple sets of data.

A better way (recursion)

Recursive method and three layers of loop is actually about the same, but also a little increase the possibility of permutation combination, code 👇 :

var letterCombinations = function(digits) { var obj = { 2: ['a', 'b', 'c'], 3: ['d', 'e', 'f'], 4: ['g', 'h' ,'i'], 5: ['j', 'k', 'l'], 6: ['m', 'n', 'o'], 7: ['p', 'q', 'r', 's'], 8: ['t', 'u', 'v'], 9: ['w', 'x', 'y', 'z'] } res = [] function dfs(str, // return < digits && res.push(STR) return} var letters = digits && res.push(STR) return < digits && res.push(STR) return obj[digits[i]] for (const letter of letters) { dfs(`${str}${letter}`, i + 1) } } dfs('', 0) return res };Copy the code

The recursion is very simple. The recursion function takes two arguments, one is STR, which is the current location, and I is the current location.

If I is beyond the length of digits, insert res directly into the current string, ending the recursion. Otherwise, loop through the array of letters represented by I, start persorting and combining with STR, and continue recursion.

In terms of performance, recursion takes slightly less than 30% of the loop time, and memory consumption is about the same.

Other is not what, not very difficult one, purely the author think more.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ