Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Topic describes

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.

Their thinking

The final requirement is to arrange the numbers in the supplied string (S) in the order in which they appear. Because each number has its mapping relationship, the dictionary table is established for quick query.

1. DFS state tree

As long as the termination condition is not met (either 0, 1, or the length of the current combination is inconsistent with the length of S), the uncombination continues to generate new branches

var letterCombinations = function(digits) {

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

let result = [];

const dfs = (str, index) = > {
    // If index is equal to the original string, the current branch has been combined
    // We can finish the recursion
    if(index >= digits.length) {
        result.push(str)
        return
    }
    // Get the set of letters corresponding to the current number
    let map = dictionary[digits[index]];
    // handle exception boundaries such as 1 and 0
    if(map) {
        // Each element in the current letter set and more character combinations generated in the upper recursion
        for(let i of map) {
            // Move the position where you want to join the group backwards
            dfs(str+i, index+1); }}}// Start from the first position in the string
dfs(' '.0);

return result
};
Copy the code

2. BFS state tree

Each time, the combination state of the current layer is collected and used as a reference value for the generation of new combinations for the next layer

var letterCombinations = function(digits) {
 if(digits.length === 0) {
    return[]}const dictionary = {
    2: 'abc'.3: 'def'.4: 'ghi'.5: 'jkl'.6: 'mno'.7: 'pqrs'.8: 'tuv'.9: 'wxyz'
}
let result = [];
// bfs    
// if the first digit is 1 or 0
// Generate the initial combination reference value to facilitate the use of the while loop (manually initializing the iteration stack)
if(digits[0] && digits[0]! = =1) { result.push(... dictionary[digits[0]]);
}
let index = 1, map, temp;
while (index < digits.length) {
    // Get the set of letters corresponding to the current number
    map = dictionary[digits[index]];
    if(map) {
        // Record all combinations of the current layer
        temp = []
        for (let i = 0; i < map.length; i++) {
            for(let j = 0; j < result.length; j++) {
                // The combination state generated based on the combination condition corresponding to the previous numbertemp.push(result[j] + map[i]); }}// Update the status of the group
        result = temp;
    }else {
        // the 0, 1 loop terminates
        break;
    }
    // Update index to get the value of the next position
    index++;
}

return result
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤