Problem 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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1

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

Example 2

Input: digits = ""
Output: []

Solution

This is a straightforward problem. To find all combinations, we can think of it as a tree, and we go from the root to the leaf where each node has 3-4 children. Therefore, we can use depth-first-search to scan all possible paths.

Java Code

class Solution {
    private Map<String, String> map = Map.of("2", "abc", "3", "def", "4", "ghi", "5", "jkl", "6", "mno", "7", "pqrs", "8", "tuv", "9", "wxyz");
    List<String> ret = new ArrayList<String>();
    String input="";

    public List<String> letterCombinations(String digits) {
        if( digits.length() == 0 ) return ret;
        
        input = digits;
        buildLetters(0, new StringBuilder());
        
        return ret;
    }

    private void buildLetters(int index, StringBuilder str){

        if(str.length() == input.length()){
            ret.add(str.toString());
            return;
        }

        String letters = map.get( input.substring(index, index+1) );
        for(int i=0; i<letters.length(); i++){
            str.append( letters.substring(i,i+1) );
            buildLetters(index+1, str);
            str.deleteCharAt( str.length()-1 );
        }
    }
}