Letter Combinations Of A Phone Number

                                            
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if(digits.empty()) {
            return result;
        }
        
        vector<string> mappings = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        string combination = "";
        backtrack(result, mappings, digits, combination, 0);
        
        return result;
    }
    
    void backtrack(vector<string>& result, vector<string>& mappings, string& digits, string& combination, int index) {
        if(index == digits.length()) {
            result.push_back(combination);
            return;
        }
        
        string letters = mappings[digits[index] - '0'];
        for(char c : letters) {
            combination.push_back(c);
            backtrack(result, mappings, digits, combination, index + 1);
            combination.pop_back();
        }
    }
};

                                            
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        
        String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        backtrack(digits, mapping, result, new StringBuilder(), 0);
        
        return result;
    }
    
    private void backtrack(String digits, String[] mapping, List<String> result, StringBuilder sb, int index) {
        if (index == digits.length()) {
            result.add(sb.toString());
            return;
        }
        
        String letters = mapping[digits.charAt(index) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            sb.append(letters.charAt(i));
            backtrack(digits, mapping, result, sb, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

                                            
class Solution:
    def letterCombinations(self, digits):
        if not digits:
            return []
        
        mapping = {
            '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']
        }
        
        def backtrack(combination, next_digits):
            if len(next_digits) == 0:
                output.append(combination)
            else:
                for letter in mapping[next_digits[0]]:
                    backtrack(combination + letter, next_digits[1:])
        
        output = []
        backtrack("", digits)
        return output

                                            
/**
 * Note: The returned array must be malloced, assume caller calls free
().
 */
char** letterCombinations(char* digits, int* returnSize) {
    char* mapping[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int numDigits = strlen(digits);
    if (numDigits == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int totalCombinations = 1;
    for (int i = 0; i < numDigits; i++) {
        int index = digits[i] - '2';
        totalCombinations *= strlen(mapping[index]);
    }
    
    char** result = (char**)malloc(sizeof(char*) * totalCombinations);
    for (int i = 0; i < totalCombinations; i++) {
        result[i] = (char*)malloc(sizeof(char) * (numDigits + 1));
    }
    
    *returnSize = totalCombinations;
    
    int* indexArray = (int*)malloc(sizeof(int) * numDigits);
    memset(indexArray, 0, sizeof(int) * numDigits);
    
    for (int i = 0; i < totalCombinations; i++) {
        for (int j = 0; j < numDigits; j++) {
            int index = digits[j] - '2';
            result[i][j] = mapping[index][indexArray[j]];
        }
        
        for (int j = numDigits - 1; j >= 0; j--) {
            indexArray[j]++;
            if (indexArray[j] < strlen(mapping[digits[j] - '2'])) {
                break;
            } else {
                indexArray[j] = 0;
            }
        }
    }
    
    for (int i = 0; i < totalCombinations; i++) {
        result[i][numDigits] = '\0';
    }
    
    free(indexArray);
    
    return result;
}

                                            
public class Solution {
    public IList<string> LetterCombinations(string digits) {
        IList<string> result = new List<string>();
        if (string.IsNullOrEmpty(digits)) {
            return result;
        }
        
        string[] mappings = new string[] {
            "", 
            "", 
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        
        GenerateCombinations(digits, mappings, 0, "", result);
        
        return result;
    }
    
    private void GenerateCombinations(string digits, string[] mappings, int index, string current, IList<string> result) {
        if (index == digits.Length) {
            result.Add(current);
            return;
        }
        
        string letters = mappings[digits[index] - '0'];
        for (int i = 0; i < letters.Length; i++) {
            GenerateCombinations(digits, mappings, index + 1, current + letters[i], result);
        }
    }
}

                                            
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (digits.length === 0) return [];
    
    const map = {
        '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']
    };
    
    let result = [''];
    
    for (let digit of digits) {
        const letters = map[digit];
        let tempResult = [];
        for (let letter of letters) {
            for (let item of result) {
                tempResult.push(item + letter);
            }
        }
        result = tempResult;
    }
    
    return result;
};

                                            
function letterCombinations(digits: string): string[] {
    const map: { [key: string]: string[] } = {
        '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 result: string[] = [];

    const backtrack = (index: number, current: string) => {
        if (index === digits.length) {
            if (current.length > 0) {
                result.push(current);
            }
            return;
        }

        const letters = map[digits[index]];

        for (let i = 0; i < letters.length; i++) {
            backtrack(index + 1, current + letters[i]);
        }
    };

    if (digits.length > 0) {
        backtrack(0, '');
    }

    return result;
};

                                            
class Solution {
    /**
     * @param String $digits
     * @return String[]
     */
    function letterCombinations($digits) {
        if (empty($digits)) {
            return [];
        }
        
        $mapping = [
            '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'],
        ];
        
        $output = [''];
        
        for ($i = 0; $i < strlen($digits); $i++) {
            $temp = [];
            foreach ($output as $prev) {
                foreach ($mapping[$digits[$i]] as $char) {
                    $temp[] = $prev . $char;
                }
            }
            $output = $temp;
        }
        
        return $output;
    }
}

                                            
class Solution {
    func letterCombinations(_ digits: String) -> [String] {
        guard !digits.isEmpty else {
            return []
        }
        
        let mappings: [Character: [String]] = [
            "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"]
        ]
        
        var result: [String] = []
        
        func backtrack(_ index: Int, _ current: String) {
            if index == digits.count {
                result.append(current)
                return
            }
            
            let digit = digits[digits.index(digits.startIndex, offsetBy: index)]
            if let letters = mappings[digit] {
                for letter in letters {
                    backtrack(index + 1, current + letter)
                }
            }
        }
        
        backtrack(0, "")
        
        return result
    }
}

                                            
class Solution {
    fun letterCombinations(digits: String): List<String> {
        if (digits.isEmpty()) {
            return emptyList()
        }
        
        val phoneMap = mapOf(
            '2' to listOf("a", "b", "c"),
            '3' to listOf("d", "e", "f"),
            '4' to listOf("g", "h", "i"),
            '5' to listOf("j", "k", "l"),
            '6' to listOf("m", "n", "o"),
            '7' to listOf("p", "q", "r", "s"),
            '8' to listOf("t", "u", "v"),
            '9' to listOf("w", "x", "y", "z")
        )
        
        val result = mutableListOf<String>()
        generateCombinations("", digits, phoneMap, result)
        
        return result
    }
    
    private fun generateCombinations(current: String, remaining: String, phoneMap: Map<Char, List<String>>, result: MutableList<String>) {
        if (remaining.isEmpty()) {
            result.add(current)
            return
        }
        
        val digit = remaining[0]
        val letters = phoneMap[digit]
        
        letters?.forEach { letter ->
            generateCombinations(current + letter, remaining.substring(1), phoneMap, result)
        }
    }
}

                                            
class Solution {
  List<String> letterCombinations(String digits) {
    List<String> result = [];
    if (digits.isEmpty) {
      return result;
    }
    
    Map<String, List<String>> phoneMap = {
      '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']
    };
    
    void backtrack(int index, String current) {
      if (index == digits.length) {
        result.add(current);
        return;
      }
      
      String digit = digits[index];
      for (int i = 0; i < phoneMap[digit]!.length; i++) {
        backtrack(index + 1, current + phoneMap[digit]![i]);
      }
    }
    
    backtrack(0, '');
    
    return result;
  }
}

                                            
func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }

    phone := map[byte]string{
        '2': "abc",
        '3': "def",
        '4': "ghi",
        '5': "jkl",
        '6': "mno",
        '7': "pqrs",
        '8': "tuv",
        '9': "wxyz",
    }

    var result []string
    var backtrack func(combination string, nextDigits string)

    backtrack = func(combination string, nextDigits string) {
        if len(nextDigits) == 0 {
            result = append(result, combination)
        } else {
            digit := nextDigits[0]
            letters := phone[digit]
            for i := 0; i < len(letters); i++ {
                letter := phone[digit][i]
                backtrack(combination+string(letter), nextDigits[1:])
            }
        }
    }

    backtrack("", digits)
    return result
}

                                            
# @param {String} digits
# @return {String[]}
def letter_combinations(digits)
    return [] if digits.empty?
    
    phone = {
        '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']
    }
    
    result = ['']
    digits.chars.each do |digit|
        temp = []
        result.each do |res|
            phone[digit].each do |char|
                temp << res + char
            end
        end
        result = temp
    end
    
    return result
end

                                            
object Solution {
    def letterCombinations(digits: String): List[String] = {
        val phoneMap = Map(
            '2' -> List("a", "b", "c"),
            '3' -> List("d", "e", "f"),
            '4' -> List("g", "h", "i"),
            '5' -> List("j", "k", "l"),
            '6' -> List("m", "n", "o"),
            '7' -> List("p", "q", "r", "s"),
            '8' -> List("t", "u", "v"),
            '9' -> List("w", "x", "y", "z")
        )

        def combine(prefix: String, suffix: String): List[String] = {
            if (suffix.isEmpty) {
                List(prefix)
            } else {
                val currentDigit = suffix.head
                val currentLetters = phoneMap(currentDigit)
                currentLetters.flatMap(letter => combine(prefix + letter, suffix.tail))
            }
        }

        if (digits.isEmpty) {
            List()
        } else {
            combine("", digits)
        }
    }
}

                                            
impl Solution {
    pub fn letter_combinations(digits: String) -> Vec<String> {
        let mut result = vec![];
        if digits.is_empty() {
            return result;
        }
        
        let mapping: Vec<&str> = vec!["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
        
        fn backtrack(result: &mut Vec<String>, mapping: &Vec<&str>, digits: &str, current: String, index: usize) {
            if index == digits.len() {
                result.push(current);
                return;
            }
            
            let digit = digits.chars().nth(index).unwrap() as usize - '2' as usize;
            for letter in mapping[digit].chars() {
                let new_current = current.clone() + &letter.to_string();
                backtrack(result, mapping, digits, new_current, index + 1);
            }
        }
        
        backtrack(&mut result, &mapping, &digits, String::new(), 0);
        
        result
    }
}

To solve this coding challenge, we need to generate all possible letter combinations that can be represented by a given string of digits from 2-9. Each digit corresponds to a set of letters, similar to the old telephone keypads. For instance, the digit '2' maps to the letters 'a', 'b', and 'c'. The task is to take a string of these digits and output all possible combinations of letters that the string could form.

Explanation

This problem is essentially a backtracking problem where we explore all potential combinations of letters for the input digits. The backtracking approach systematically searches for all solutions, exploring each possibility part by part and backtracking as soon as it determines that a particular partial solution cannot be extended to a valid solution. To approach this problem:

Mapping Digits to Letters : First, we need to map each digit to its corresponding letters.
Backtracking Function : We create a recursive function,
backtrack

, which constructs the letter combinations.
Recursive Construction : At each step of the recursion, the function takes a partial combination and the remaining digits. For each letter corresponding to the current digit, it appends the letter to the partial combination and recurses with the rest of the digits.
Base Case : When there are no more digits left to process, the current partial combination is a complete combination, and we store it.
Initialization and Output : Initialize the process and collect all resulting combinations.

Example Walkthrough

Consider the input "23":

The digit '2' maps to ['a', 'b', 'c']
The digit '3' maps to ['d', 'e', 'f']

We start with an empty combination and "23" as digits:

Append 'a' to the current combination and recurse with "3":

Append 'd' to 'a' resulting in "ad", and since there are no more digits, store "ad".
Append 'e' to 'a' resulting in "ae", and store "ae".
Append 'f' to 'a' resulting in "af", and store "af".

Now, append 'b' to the current combination and recurse with "3":

Repeat the same as step 1 for 'b', generating "bd", "be", "bf".

Finally, append 'c' and repeat, producing "cd", "ce", "cf".

In the end, we have all possible combinations ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Detailed Steps in Pseudocode

Define a digit-to-character mapping :

                                            
mapping = {
'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']
}

Initialize an output list to store combinations :

                                            
output = []

Define the backtracking function :

                                            
function backtrack(combination, next_digits):
# Base case: if no more digits left, store the current combination
if length(next_digits) == 0:
add combination to output
else:
# Iterate over all letters mapped to the current digit
for each letter in mapping[next_digits[0]]:
# Append current letter to combination and recurse with remaining digits
backtrack(combination + letter, substring(next_digits, 1))

Handle edge case for empty input and initiate the process :

                                            
# If input digits are empty, return empty list
if length(digits) == 0:
    return []

# Start backtracking with an empty combination and the input digits
backtrack("", digits)

# Return the list of combinations
return output

This pseudocode provides a structured approach using backtracking to explore all combinations formed by the digits-to-letters mapping, effectively solving the problem.