Letter Combinations of a Phone Number

Intuition

Imagine needing to create all possible words using the letters associated with each digit on a telephone keypad. Start with an empty word and choose a letter from the set of letters corresponding to the first digit, then move to the next digit, and continue until there are no more digits. This process is repeated for each combination of letters, resulting in all possible words.

Begin by thinking of the problem as constructing words step by step. Start with an empty string and at each step, append a letter corresponding to the current digit. Progress to the next digit and repeat the process. When the end of the digit string is reached, a complete word has been formed. This recursive approach mimics a systematic way of exploring all possible combinations by building words character by character, moving through each digit's letters in turn, and backtracking when necessary to explore new combinations.

Approach

Initialize a mapping of digits to their corresponding letters, and an empty list to store results.
Define a recursive helper function that takes the current digit index, the current string combination, and the result list as arguments.
In the base case, when the index equals the length of the digits string, add the current combination to the result list.
For the current digit, iterate over its corresponding letters and recursively call the helper function with the next index and the updated combination string.

Dry run

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Recursive function to generate letter combinations
    void func(int ind, string digits, string s, vector<string> &ans, string combos[]) {
        // Base case: if index reaches the end of digits
        if(ind == digits.size()) {
            // Add the current combination to the answer
            ans.push_back(s);
            return;
        }
        // Convert the current character to an integer
        int digit = digits[ind] - '0';
        // Loop through the corresponding characters
        for(int i = 0; i < combos[digit].size(); i++) {
            // Recursively call function with next index
            // Add current character to the string
            func(ind + 1, digits, s + combos[digit][i], ans, combos);
        }
    }

public:
    // Function to get all letter combinations for a given digit string
    vector<string> letterCombinations(string digits) {
        // Mapping digits to corresponding characters
        string combos[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> ans; // Vector to store results
        string s = ""; // Temporary string to build combinations
        // Initiate recursive function
        func(0, digits, s, ans, combos);
        return ans; // Return the result
    }
};

int main() {
    Solution solution;
    string digits = "23"; // Input digits
    vector<string> result = solution.letterCombinations(digits); // Get combinations

    // Print the results
    for (const string& combination : result) {
        cout << combination << " ";
    }
    return 0;
}
import java.util.ArrayList;
import java.util.List;

class Solution {
    private final String[] map;

    public Solution() {
        // Mapping digits to corresponding characters
        map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    }

    // Recursive helper function to generate combinations
    private void helper(String digits, List<String> ans, int index, String current) {
        // Base case: if index reaches the end of digits
        if (index == digits.length()) {
            // Add the current combination to the answer
            ans.add(current);
            return;
        }
        // Get characters corresponding to the current digit
        String s = map[digits.charAt(index) - '0'];
        // Loop through the corresponding characters
        for (int i = 0; i < s.length(); i++) {
            // Recursively call function with next index
            // Add current character to the string
            helper(digits, ans, index + 1, current + s.charAt(i));
        }
    }

    // Function to get all letter combinations for a given digit string
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>(); // List to store results
        // Return empty list if digits string is empty
        if (digits.length() == 0) return ans;
        // Initiate recursive function
        helper(digits, ans, 0, "");
        return ans; // Return the result
    }

    // Main method to demonstrate the usage of the Solution class
    public static void main(String[] args) {
        Solution solution = new Solution();
        String digits = "23"; // Input digits
        List<String> result = solution.letterCombinations(digits); // Get combinations

        // Print the results
        for (String combination : result) {
            System.out.print(combination + " ");
        }
    }
}
class Solution:
    def __init__(self):
        # Mapping digits to corresponding characters
        self.map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

    # Recursive helper function to generate combinations
    def helper(self, digits, ans, index, current):
        # Base case: if index reaches the end of digits
        if index == len(digits):
            # Add the current combination to the answer
            ans.append(current)
            return
        # Get characters corresponding to the current digit
        s = self.map[int(digits[index])]
        # Loop through the corresponding characters
        for char in s:
            # Recursively call function with next index
            # Add current character to the string
            self.helper(digits, ans, index + 1, current + char)

    # Function to get all letter combinations for a given digit string
    def letterCombinations(self, digits):
        ans = []  # List to store results
        # Return empty list if digits string is empty
        if not digits:
            return ans
        # Initiate recursive function
        self.helper(digits, ans, 0, "")
        return ans  # Return the result

# Main section to demonstrate the usage of the Solution class
if __name__ == "__main__":
    solution = Solution()
    digits = "23"  # Input digits
    result = solution.letterCombinations(digits)  # Get combinations

    # Print the results
    print(result)
class Solution {
    constructor() {
        // Mapping digits to corresponding characters
        this.map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    }

    // Recursive helper function to generate combinations
    helper(digits, ans, index, current) {
        // Base case: if index reaches the end of digits
        if (index === digits.length) {
            // Add the current combination to the answer
            ans.push(current);
            return;
        }
        // Get characters corresponding to the current digit
        let s = this.map[digits[index] - '0'];
        // Loop through the corresponding characters
        for (let i = 0; i < s.length; i++) {
            // Recursively call function with next index
            // Add current character to the string
            this.helper(digits, ans, index + 1, current + s[i]);
        }
    }

    // Function to get all letter combinations for a given digit string
    letterCombinations(digits) {
        let ans = []; // Array to store results
        // Return empty array if digits string is empty
        if (digits.length === 0) return ans;
        // Initiate recursive function
        this.helper(digits, ans, 0, "");
        return ans; // Return the result
    }
}

// Main section to demonstrate the usage of the Solution class
const solution = new Solution();
const digits = "23"; // Input digits
const result = solution.letterCombinations(digits); // Get combinations

// Print the results
console.log(result);

Complexity Analysis

Time Complexity O(4^N * N), where n is the length of the input digits. This is because each digit can map to up to 4 letters and there are n digits.

Space Complexity: O(N), where n is the length of the input digits. This is due to the recursion stack depth.

Problem List

Letter Combinations of a Phone Number

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code