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.

The sample

Example 1: input: who = “23” output: [” AD “, “ae”, “af”, “bd”, “be”, “bf”, “CD” and “ce”, “cf”]

Example 2: Input: digits = “” Output: []

Example 3: Input: digits = “2” Output: [“a”,”b”,” C “]

Tip: 0 <= digits. Length <= 4 digits[I] is a number in the range [‘2’, ‘9’].

Source: LeetCode link: leetcode-cn.com/problems/le…

Analysis of the

According to the description of the problem, all permutations need to be found, so the backtracking algorithm is used to solve the problem, and the steps are as follows:

  1. Create space result to hold the last result set and perRes to hold the current result string
  2. Backtracking algorithm, deep search processing

implementation

void backTrack(char *digits, int *returnSize, char *perRes, char **result, int idx, char **map)
{
    // The last layer of letters has been combined. Adds the current result string to the result set
    if (idx == strlen(digits)) {
        result[*returnSize] = (char*)malloc(sizeof(char) * (strlen(digits) + 1));
        strcpy(result[*returnSize], perRes);
        (*returnSize)++;
        return;
    }
    int num = digits[idx] - '0';   // Get the current number
    for (int i = 0; i < strlen(map[num]); i++) { // The number of cycles is the number of letters corresponding to the number of nodes in the current layer
        strncat(perRes, &map[num][i], 1);  // Add one of the letters corresponding to the number of the current node to the result string
        idx++;     // layer +1 to find the node at the next layer
        backTrack(digits, returnSize, perRes, result, idx, map); // Go back to the next level
        perRes[--idx] = '\ 0';       // go to the next node at the first level
    }
    return;
}

char **letterCombinations(char *digits, int *returnSize)
{
    *returnSize = 0;
    
    // Map [2] corresponds to ABC
    char *map[10] = {"\ 0"."\ 0"."abc"."def"."ghi"."jkl"."mno"."pqrs"."tuv"."wxyz"};
    int strLen = strlen(digits);
    
    // Store the current result string
    char *perRes = (char*)malloc(sizeof(char) * (strLen + 1));      // Store one of the combinations
    memset(perRes, 0.sizeof(char) * (strLen + 1));
    
    // Store the result set containing multiple perRes strings
    char **result = (char* *)malloc(sizeof(char*) * pow(4, strLen)); // Store the result set
    memset(result, 0.sizeof(char*) * pow(4, strLen));
    if (digits == NULL || strlen(digits) < 1) {
        *returnSize = 0;
        return NULL;
    }
    backTrack(digits, returnSize, perRes, result, 0.map);
    return result;
}
Copy the code