Letter Combinations of a Phone Number

MEDIUM

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Mobile Keypad

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].
/**
    Input: digits = "23"
    Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
**/

class Solution {
    
    private Map<String, String> keyboard = new HashMap<>();
    
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits == null || digits.isEmpty()){
            return result;
        }
        populateKeyBoard();
        String current = "";
        int n = digits.length();
        generateLetterCombinations(result, current, digits, n);
        return result;
    }
    
    private void generateLetterCombinations(List<String> result, String current, String 
                 remaining_digits, int n){
        if(current.length() == n){
            result.add(current);
        }else{
            String curDigit = remaining_digits.substring(0, 1);
            String curMapping = keyboard.get(curDigit);
            int len = curMapping.length();
            for(int i = 0 ; i < len ; i++){
                String cur = String.valueOf(curMapping.charAt(i));
                generateLetterCombinations(result, (current + cur), 
                remaining_digits.substring(1), n);
            }
        }
    }
    
    private void populateKeyBoard(){
        keyboard.put("2", "abc");
        keyboard.put("3", "def");
        keyboard.put("4", "ghi");
        keyboard.put("5", "jkl");
        keyboard.put("6", "mno");
        keyboard.put("7", "pqrs");
        keyboard.put("8", "tuv");
        keyboard.put("9", "wxyz");
    }
}

Complexity Analysis

  • Time Complexity : O(3N × 4M) where N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9), and N+M is the total number digits in the input.
  • Space Complexity : O(3N × 4M) since one has to keep 3N × 4M solutions.

Categories: Backtracking

Tagged as:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s