Letter Combinations of a Phone Number In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Skylinewebz

Problem Statement: Letter Combinations of a Phone Number

Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent. A mapping of digits to letters (just like on the telephone buttons) is given below.

  • 2 maps to ["a", "b", "c"]
  • 3 maps to ["d", "e", "f"]
  • 4 maps to ["g", "h", "i"]
  • 5 maps to ["j", "k", "l"]
  • 6 maps to ["m", "n", "o"]
  • 7 maps to ["p", "q", "r", "s"]
  • 8 maps to ["t", "u", "v"]
  • 9 maps to ["w", "x", "y", "z"]

The output should return all possible combinations of letters that can be formed by the digits in the input string.

Example:

Input:

digits = "23"

Output:

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Input:

digits = ""

Output:

[]

Input:

digits = "2"

Output:

["a", "b", "c"]

Approach:

The problem can be approached by using backtracking or iterative combination generation. We can build the combinations step by step by taking one letter from each digit’s corresponding character set.

  1. Backtracking:
    • Start with the first digit, and for each letter corresponding to the digit, recursively proceed to the next digit, adding the current letter to the combination.
    • Once all digits have been processed, store the combination.
  2. Iterative Combination:
    • Start with an empty combination list, and for each digit, iterate over the current combinations and append the new letters that correspond to the digit.
    • This is similar to performing a Cartesian product across the characters of each digit.

Steps:

  1. Map Digits to Letters: Use a dictionary to map each digit to its corresponding letters.
  2. Use Backtracking or Iteration: For each digit, either generate combinations using recursion or iteratively build them.
  3. Edge Cases:
    • If the input is an empty string, return an empty list.
    • Handle input strings with multiple digits.

Time Complexity:

  • Time Complexity: O(3N)O(3^N)O(3N), where NNN is the number of digits in the input. In the worst case, each digit can map to 4 letters, so the number of combinations grows exponentially with the length of the string.
  • Space Complexity: O(3N)O(3^N)O(3N) for storing the result, plus the recursion stack in case of backtracking.

Code Implementation

C Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const char* digitToChar[] = {
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

void backtrack(char* digits, int index, char* current, char** result, int* returnSize) {
    if (index == strlen(digits)) {
        result[*returnSize] = (char*)malloc(strlen(current) + 1);
        strcpy(result[*returnSize], current);
        (*returnSize)++;
        return;
    }
    
    int digit = digits[index] - '0';
    for (int i = 0; i < strlen(digitToChar[digit]); i++) {
        current[index] = digitToChar[digit][i];
        backtrack(digits, index + 1, current, result, returnSize);
    }
}

char** letterCombinations(char* digits, int* returnSize) {
    if (digits == NULL || strlen(digits) == 0) {
        *returnSize = 0;
        return NULL;
    }

    char** result = (char**)malloc(1000 * sizeof(char*)); // Assumption of max size
    char* current = (char*)malloc(strlen(digits) + 1);

    *returnSize = 0;
    backtrack(digits, 0, current, result, returnSize);
    free(current);
    
    return result;
}

int main() {
    char digits[] = "23";
    int returnSize;
    char** result = letterCombinations(digits, &returnSize);
    
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", result[i]);
        free(result[i]);
    }
    free(result);
    
    return 0;
}

C++ Code:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if (digits.empty()) return result;

        vector<string> digitToChar = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };
        
        string current;
        backtrack(digits, 0, current, result, digitToChar);
        return result;
    }

private:
    void backtrack(const string& digits, int index, string& current, vector<string>& result, const vector<string>& digitToChar) {
        if (index == digits.size()) {
            result.push_back(current);
            return;
        }
        
        int digit = digits[index] - '0';
        for (char c : digitToChar[digit]) {
            current.push_back(c);
            backtrack(digits, index + 1, current, result, digitToChar);
            current.pop_back();
        }
    }
};

int main() {
    Solution solution;
    vector<string> result = solution.letterCombinations("23");
    
    for (const string& combination : result) {
        cout << combination << endl;
    }
    
    return 0;
}

Java Code:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private static final String[] DIGIT_TO_CHAR = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;
        
        StringBuilder current = new StringBuilder();
        backtrack(digits, 0, current, result);
        
        return result;
    }

    private void backtrack(String digits, int index, StringBuilder current, List<String> result) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }
        
        int digit = digits.charAt(index) - '0';
        for (char c : DIGIT_TO_CHAR[digit].toCharArray()) {
            current.append(c);
            backtrack(digits, index + 1, current, result);
            current.deleteCharAt(current.length() - 1); // Backtrack
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> result = solution.letterCombinations("23");
        
        for (String combination : result) {
            System.out.println(combination);
        }
    }
}

Python Code:

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        digit_to_char = [
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        ]
        
        result = []
        self._backtrack(digits, 0, "", result, digit_to_char)
        return result

    def _backtrack(self, digits: str, index: int, current: str, result: List[str], digit_to_char: List[str]):
        if index == len(digits):
            result.append(current)
            return
        
        digit = int(digits[index])
        for char in digit_to_char[digit]:
            self._backtrack(digits, index + 1, current + char, result, digit_to_char)

# Example usage
solution = Solution()
print(solution.letterCombinations("23"))

C# Code:

using System;
using System.Collections.Generic;

public class Solution {
    private static readonly string[] DigitToChar = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public IList<string> LetterCombinations(string digits) {
        var result = new List<string>();
        if (string.IsNullOrEmpty(digits)) return result;
        
        Backtrack(digits, 0, "", result);
        return result;
    }

    private void Backtrack(string digits, int index, string current, IList<string> result) {
        if (index == digits.Length) {
            result.Add(current);
            return;
        }
        
        int digit = digits[index] - '0';
        foreach (char c in DigitToChar[digit]) {
            Backtrack(digits, index + 1, current + c, result);
        }
    }

    public static void Main() {
        Solution solution = new Solution();
        var result = solution.LetterCombinations("23");
        
        foreach (var combination in result) {
            Console.WriteLine(combination);
        }
    }
}

JavaScript Code:

var letterCombinations = function(digits) {
    if (digits === "") return [];
    
    const digitToChar = [
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    ];
    
    let result = [];
    
    function backtrack(index, current) {
        if (index === digits.length) {
            result.push(current);
            return;
        }
        
        let digit = digits[index] - '0';
        for (let char of digitToChar[digit]) {
            backtrack(index + 1, current + char);
        }
    }
    
    backtrack(0, "");
    return result;
};

// Example usage
console.log(letterCombinations("23"));

Explanation:

  1. Mapping Digits to Characters: We have an array (or dictionary) that maps digits to their corresponding letters.
  2. Backtracking: We start from the first digit, pick each character from the corresponding string, and recursively try all combinations for the next digit.
  3. Edge Case Handling: If the input string is empty, we return an empty list.

Time Complexity:

  • Time Complexity: O(3^N)) in the worst case, where NNN is the number of digits in the input. Each digit can have 3 or 4 characters (depending on the digit).
  • Space Complexity: O(3^N) for storing the combinations.