LeetCode //C - 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = “23”
Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

Example 2:

Input: digits = “”
Output: []

Example 3:

Input: digits = “2”
Output: [“a”,“b”,“c”]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range [‘2’, ‘9’].

From: LeetCode
Link: 17. Letter Combinations of a Phone Number

---

Solution:

Ideas：

1. Mapping:

• A 2D array mapping is used to map digits from ‘2’ to ‘9’ to their corresponding letters.

2. Calculate Total Combinations:

• The variable total is used to calculate the total number of combinations. This is done by multiplying the lengths of the strings that each digit maps to. For the string “23”, this would be 3×3=9 (since “2” maps to “abc” and “3” maps to “def”).

3. Generate Combinations:

• The main logic is in this part. We iterate i from 0 to total-1 and for each value of i, we generate one combination.
• For each digit in the input, we determine which letter it should map to using modular arithmetic. This is essentially converting i into a number in our mixed-radix system.
• We use a variable temp to keep track of the current radix. For each digit, we use the formula mapping[digits[j] - ‘2’][(i / temp) % len] to determine which letter to pick. The division by temp shifts our focus to the correct digit position, and the modulo operation (% len) gives us the index of the letter to use for the current digit.
• After picking the letter, we multiply temp by len to update the radix for the next position.

4. Main Function:

• This is just a demonstration of how to use the letterCombinations function. It calls the function with the input “23”, prints the resulting combinations, and then frees the allocated memory.

Code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** letterCombinations(char * digits, int* returnSize) {
    if (!digits || strlen(digits) == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    char* mapping[] = {
        "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };
    
    int total = 1;
    for (int i = 0; i < strlen(digits); i++) {
        total *= strlen(mapping[digits[i] - '2']);
    }
    
    *returnSize = total;
    char** result = (char**) malloc(total * sizeof(char*));
    
    for (int i = 0; i < total; i++) {
        result[i] = (char*) malloc((strlen(digits) + 1) * sizeof(char));
        int temp = 1;
        for (int j = 0; j < strlen(digits); j++) {
            int len = strlen(mapping[digits[j] - '2']);
            result[i][j] = mapping[digits[j] - '2'][(i / temp) % len];
            temp *= len;
        }
        result[i][strlen(digits)] = '\0';
    }
    
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35