17. Letter Combinations of a Phone Number

Description

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.

Constraints

• 0 <= digits.length <= 4

• digits[i] is a digit in the range ['2', '9'].

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: digits = "23"

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

Example 2

Example 3

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private final char[][] charMap = {{}, {}, {'a', 'b', 'c'}, 
                                      {'d', 'e', 'f'}, {'g', 'h', 'i'},
                                      {'j', 'k', 'l'}, {'m', 'n', 'o'}, 
                                      {'p', 'q', 'r', 's'}, {'t', 'u', 'v'},
                                      {'w', 'x', 'y', 'z'}};
    
    public List<String> letterCombinations(String digits) {
        List<String> resultList = new ArrayList<>();
        if(digits == null || digits.isEmpty()) {
            return resultList;
        }
        letterCombinations(digits, 0, new StringBuilder(), resultList);
        return resultList;
    }
    
    private void letterCombinations(String digits,  
                                    int index, 
                                    StringBuilder combSB, 
                                    List<String> resultList) {
        if(index == digits.length()) {
            resultList.add(combSB.toString());
            return;
        }
        
        int digitIndex = digits.charAt(index)-'0';
        for(char ch: charMap[digitIndex]) {
            combSB.append(ch);
            letterCombinations(digits, index+1, combSB, resultList);
            combSB.deleteCharAt(index);
        }
    }
}

Follow up