“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

Hello, everyone. Today, I’m going to share with you the next LeetCode medium difficulty problem.

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.

Analysis of the

1. Each number corresponds to a letter set, which contains only numbers from 2 to 9

2. Select one letter corresponding to each number in each combination

3. Return an array containing various combinations

solution

1. The recursion

Solution a:recursive

Idea 1. First create a dictionary mapping containing arrays and letters. 2. Do the following steps at each level of recursion. When the index of cur corresponding to the termination condition is the same as the digit of digits, it is one of the required combinations to be placed in the RES 2. Retrieves the corresponding alphabetic array 3 in the current digits[cur] based on the index cur. Return string */ var lettercolumn = function (digits) {if (! digits) return []; / / initialize the dictionary const dic = {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"], }; const res = []; // split array const digitsArr = digits.split(""); function recur(arr, If (cur === digitsarr.length) {res.push(arr.join("")); // if (cur == digitsarr.length) {res.push(arr.join("")); return; DigitsArr [cur]; digitsArr[cur]; digitsArr[cur]; digitsArr[cur]; digitsArr[cur]; digitsArr[cur]; digitsArr[cur]; const letters = dic[digit]; Cur +1 for (let j = 0; j < letters.length; j++) { const letter = letters[j]; recur([...arr, letter], cur + 1); } } recur([], 0); return res; }; /* Complexity time O(3^m x 4^m) where m is the number of three letters in the input and n is the number of four letters in the input space O(m+n) */Copy the code

conclusion

Today’s problem is mainly to practice using recursion to solve generated combinations of these kinds of problems

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

If you’re interested in “TS” check out my column (TypeScript common knowledge) and thank you for supporting it

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]