Letter Combinations of a Phone Number

class Solution {
private:
    vector<string> result;
    unordered_map<char, string> digitToLetters = {
        {'2', "abc"}, {'3', "def"},  {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
    string digitsInput;

public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) {
            return result;
        }
        digitsInput = digits;
        combineLetters(0, "");
        return result;
    }

private:
    void combineLetters(int pos, string currentCombination) {
        if (currentCombination.length() == digitsInput.length()) {
            result.push_back(currentCombination);
            return;
        }
        string currentLetters = digitToLetters[digitsInput[pos]];
        for (char letter : currentLetters) {
            currentCombination.push_back(letter);
            combineLetters(pos + 1, currentCombination);
            currentCombination.pop_back();
        }
    }
};

The given C++ code defines a solution for generating all possible letter combinations that a given number string could represent on a phone keypad. Here's a detailed breakdown of how the code operates:

• An instance of unordered_map named digitToLetters maps each digit from '2' to '9' to its corresponding string of letters. This map is used to retrieve possible letter choices for phone digits.

• The class has a private member variable result which stores the final combinations of letters. Another private variable digitsInput holds the input digit string.

• The public member function letterCombinations is designed to initiate the process:

  • If the input string digits is empty, the function immediately returns the result, which will be empty.
  • The function sets digitsInput to the given digits then calls the recursive function combineLetters starting from position 0 with an empty string for accumulating combinations.

• The private function combineLetters performs the recursion:

  • It first checks if the length of the currentCombination string is equal to the length of digitsInput. If true, the current combination is complete and is added to result.
  • The function retrieves possible letters for the current digit position and iterates through each letter. The letter is added to the current combination, a recursive call is made to the next position, and the letter is then removed (backtracking) to explore other possibilities.

This method effectively combines backtracking with the use of a map to create an efficient solution for generating letter combinations based on-phone number mappings. This solution can handle any sequence of digits from '2' to '9', making it versatile for various input scenarios.

class PhoneLetterCombinations {
    private List<String> result = new ArrayList<>();
    private Map<Character, String> digitToLetters = Map.of(
        '2', "abc",
        '3', "def",
        '4', "ghi",
        '5', "jkl",
        '6', "mno",
        '7', "pqrs",
        '8', "tuv",
        '9', "wxyz"
    );
    private String inputDigits;

    public List<String> generateCombinations(String digits) {
        if (digits.isEmpty()) {
            return result;
        }

        inputDigits = digits;
        executeBacktrack(0, new StringBuilder());
        return result;
    }

    private void executeBacktrack(int index, StringBuilder currentPath) {
        if (currentPath.length() == inputDigits.length()) {
            result.add(currentPath.toString());
            return;
        }

        String letters = digitToLetters.get(inputDigits.charAt(index));
        for (char ch : letters.toCharArray()) {
            currentPath.append(ch);
            executeBacktrack(index + 1, currentPath);
            currentPath.deleteCharAt(currentPath.length() - 1);
        }
    }
}

The Java program provided addresses the problem of generating all possible letter combinations that the numbers on a phone keypad could represent. Here's an explanation of how the code successfully achieves this:

• Initialize a private List result to store the combinations.
• Create a Map digitToLetters to map each digit to its corresponding letters as per a traditional mobile phone keypad.
• Define a method generateCombinations to handle the public request. Accept the digit string from the user and check if it's empty. If not, begin the recursive backtracking with an initial call to executeBacktrack.
• The executeBacktrack function is fundamental. It uses recursion to explore all potential combinations:
  • Check if the current combination (currentPath) matches the length of the input string inputDigits. If yes, add the completed combination to result.
  • Retrieve the letters corresponding to the current digit using digitToLetters.get(inputDigits.charAt(index)).
  • Loop through these letters, recursively calling executeBacktrack to explore further combinations, then backtracking by removing the last character added.

This solution leverages recursion and backtracking to generate the letter combinations efficiently, ensuring all combinations are explored. Utilizing a StringBuilder optimizes string manipulation during backtracking.

// Required header file
struct characterMapping {
    char character; // Key for hashing
    const char* mappings; // Associated string values
    UT_hash_handle hh; // Hash handler for uthash
};

void generateCombinations(struct characterMapping** mappingTable, const char* digits, int currentDepth,
                          char* currentCombination, int combinationLength, char** resultArray, int* sizeResult) {
    if (combinationLength == strlen(digits)) {
        currentCombination[combinationLength] = '\0'; // Null terminate
        resultArray[*sizeResult] = (char*)calloc(combinationLength + 1, sizeof(char));
        strcpy(resultArray[*sizeResult], currentCombination);
        (*sizeResult)++;
        return;
    }
    struct characterMapping* entry;
    HASH_FIND(hh, *mappingTable, &digits[currentDepth], sizeof(char), entry);
    const char* charOptions = entry->mappings;
    while (*charOptions) {
        currentCombination[combinationLength] = *charOptions;
        generateCombinations(mappingTable, digits, currentDepth + 1, currentCombination, combinationLength + 1,
                             resultArray, sizeResult);
        charOptions++;
    }
}

char** findCombinations(char* digits, int* combinationCount) {
    if (strlen(digits) == 0) {
        *combinationCount = 0;
        return NULL;
    }
    struct characterMapping map2 = {'2', "abc"}, map3 = {'3', "def"}, map4 = {'4', "ghi"},
                            map5 = {'5', "jkl"}, map6 = {'6', "mno"}, map7 = {'7', "pqrs"},
                            map8 = {'8', "tuv"}, map9 = {'9', "wxyz"}, *item,
                            *hashTable = NULL;
    HASH_ADD(hh, hashTable, character, sizeof(char), &map2);
    HASH_ADD(hh, hashTable, character, sizeof(char), &map3);
    HASH_ADD(hh, hashTable, character, sizeof(char), &map4);
    HASH_ADD(hh, hashTable, character, sizeof(char), &map5);
    HASH_ADD(hh, hashTable, character, sizeof(char), &map6);
    HASH_ADD(hh, hashTable, character, sizeof(char), &map7);
    HASH_ADD(hh, hashTable, character, sizeof(char), &map8);
    HASH_ADD(hh, hashTable, character, sizeof(char), &map9);
    char** allCombinations = (char**)malloc(1024 * sizeof(char*));
    char* combinationBuffer = (char*)calloc(5, sizeof(char)); // Temporary buffer for combinations
    *combinationCount = 0;
    generateCombinations(&hashTable, digits, 0, combinationBuffer, 0, allCombinations, combinationCount);
    free(combinationBuffer);
    HASH_CLEAR(hh, hashTable);
    return allCombinations;
}

This solution generates all possible letter combinations that the numbers on a mobile phone keypad could represent, similar to the way SMS used to be typed in the pre-smartphone era. The application of this function can be to generate all potential word combinations for given digit inputs.

• Implement a structure named characterMapping that contains:

  • character representing the digit.
  • mappings which is the string of characters associated with the digit.
  • hh to handle hashing using uthash.

• Use a recursive function generateCombinations to create combinations:

  • It terminates and stores the result when the current combination length equals the input digits length.
  • Use a hash map to find the respective characters associated with a current digit.
  • Recursively call itself to explore further possible combinations by adding one more character.

• findCombinations prepares the environment for storing and generating combinations:

  • Initialize a hash table with predefined mappings from digits to letters.
  • Allocate memory for storing possible combinations.
  • Handle special cases like empty input.

• The program dynamically allocates memory for results, thus it is essential to free any allocated memory spaces to prevent memory leaks.

• This approach using hashing and recursion effectively handles the mapping and combination generation, and ensures a robust algorithm for the phone digit-to-letters mapping challenge.

var generateCombinations = function (inputDigits) {
    if (inputDigits.length === 0) {
        return [];
    }
    let result = [];
    let digitToLetters = {
        2: "abc",
        3: "def",
        4: "ghi",
        5: "jkl",
        6: "mno",
        7: "pqrs",
        8: "tuv",
        9: "wxyz",
    };
    let combine = function (currentIndex, currentCombo) {
        if (currentCombo.length === inputDigits.length) {
            result.push(currentCombo.join(""));
            return;
        }
        let currentLetters = digitToLetters[inputDigits[currentIndex]];
        for (let char of currentLetters) {
            currentCombo.push(char);
            combine(currentIndex + 1, currentCombo);
            currentCombo.pop();
        }
    };
    combine(0, []);
    return result;
};

In the given JavaScript code, a function named generateCombinations is defined to find all possible letter combinations that the number could represent based on the mapping of digits to letters on a telephone keypad. This is a typical problem when dealing with the input from devices that have a numeric keypad with associated letters, such as older mobile phones.

Here's a breakdown of how the function works:

• Start by checking if the input string inputDigits is empty. If it is, return an empty array because no digits mean no combinations.

• Initialize result as an empty array to store the final combinations of letters.

• Define a mapping digitToLetters that correlates each digit from 2 to 9 to its corresponding letters as per the telephone keypad.

• Define a helper function combine which is used to generate the combinations recursively:

  • The function takes currentIndex, which tracks the current digit in inputDigits, and currentCombo, which is the current combination of letters being formed.
  • If the length of currentCombo matches the length of inputDigits, concatenate the characters in currentCombo, add the resulting string to result, and terminate the recursion for this path.
  • Retrieve the letters corresponding to the current digit.
  • Loop through each letter, add it to currentCombo, and recursively call combine for the next digit.
  • Remove the last character to backtrack and explore other possibilities.

• The initial call to combine is made with 0 (starting index of inputDigits) and an empty array for currentCombo.

• Finally, the function returns result, containing all possible combinations.

This approach ensures that all combinations are explored using recursion and backtracking, a common technique for combinatorial problems such as generating permutations or combinations.

class Solution:
    def combineLetters(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        digit_to_char = {
            "2": "abc", "3": "def", "4": "ghi", 
            "5": "jkl", "6": "mno", "7": "pqrs", 
            "8": "tuv", "9": "wxyz"
        }

        def recurse(current_index, current_combination):
            if len(current_combination) == len(digits):
                result.append("".join(current_combination))
                return
            
            for char in digit_to_char[digits[current_index]]:
                current_combination.append(char)
                recurse(current_index + 1, current_combination)
                current_combination.pop()

        result = []
        recurse(0, [])
        return result

This Python3 solution addresses the problem of generating all possible letter combinations that a given phone number could represent based on traditional phone key mappings. The strategy uses a recursive helper function to build combinations one character at a time.

• First, handle a base case where the input is empty, returning an empty list. This avoids unnecessary computation if there are no digits to process.
• Create a mapping (dictionary) digit_to_char where each number (as a string) maps to a corresponding string of characters, representing the letters that each digit could correspond to on a phone keypad.
• Implement a recursive function recurse that takes two parameters: the current index in the digit string and the current combination of letters. This function performs the following:
  • Check if the length of the current combination matches the length of the input digits; if yes, convert the list of characters to a string and add it to the result list.
  • Iterate over each character that corresponds to the current phone digit (using digit_to_char), add the character to the current combination, and call recurse with the next index.
  • After recursion, remove the last character (backtrack) to explore the next potential character.
• Initialize an empty list result to store the complete combinations.
• Start the recursive combination building by calling recurse with an index of 0 and an empty list for collecting characters.

The use of recursion efficiently explores all possible combinations of letters, and backtracking ensures that all potential paths are considered without the need for redundant storage or duplicated effort. This implementation is effective for handling inputs corresponding to multi-character keys efficiently.