17. Letter Combinations of a Phone Number

📝 Problem Details

• Title: 17. Letter Combinations of a Phone Number
• Link: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
• Difficulty: Medium
• Tags/Categories: Backtracking

input string containing digits from 2-9 inclusive return all possible letter combinations that the number could represent number to letter mapping: 2 --> abc 3 --> def 4 --> ghi 5 --> jkl 6 --> mno 7 --> pqrs 8 --> tuv 9 --> wxyz

💭What Were My Initial Thoughts?

- *all possible* buzzword indicating an enumaration backtracking problem
- choices:
	- for each number there are either 3 or 4 choices
	- for example the number 2 has the choices of 'A' OR 'B' OR 'C'
	- we could create a hashmap that would map the number as the key to the value which would be a vector of characters
	- in our dfs, for each number, find the possible choices in the map and recursively construct letter combinations from that

💡 Explanation of Solution

- Precompute a hashmap for digit-to-letter mappings
- DFS function: recursively construct all possible letter combinations
- Backtracking: remove the last added letter before exploring the next choice

⌛ Complexity Analysis

Time Complexity: O(C^N)
- for each char (digit) in digits 
- lets call this N 
- there are C possible choices

Space Complexity: O(C^N) since we are storing all computations

💻 Implementation of Solution

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};  // Edge case: empty input
 
        unordered_map<char, string> phoneMap = {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
        
        vector<string> result;
        string current;
 
        dfs(digits, 0, current, result, phoneMap);
        return result;
    }
 
    void dfs(string& digits, int index, string& current, vector<string>& result, unordered_map<char, string>& phoneMap) {
        // Base case: if we have constructed a full-length combination
        if (current.size() == digits.size()) {
            result.push_back(current);
            return;
        }
 
        // Get the possible characters for the current digit
        string possibleChars = phoneMap[digits[index]];
 
        for (char c : possibleChars) {
            current.push_back(c);  // Choose
            dfs(digits, index + 1, current, result, phoneMap);  // Explore next digit
            current.pop_back();  // Backtrack (undo choice)
        }
    }
};