Java: Letter Combinations of a Phone Number

Thought Process

The problem requires generating all possible combinations of letters corresponding to the digits of a phone number. We use backtracking to explore all possible combinations. First, we map each digit to its corresponding letters using a dictionary. Then, we recursively build combinations by appending one letter at a time to a temporary string ( 'tmp'). When the size of 'tmp' matches the length of the input digits, we add it to the result. This ensures we explore all possible combinations without missing any. 

class Solution {

    public void backTrack(List<String> ans, Map<Integer,String> mp, String digits, StringBuilder comb, int start){

        if(comb.length()==digits.length()){
            ans.add(comb.toString());
            return;
        }

        for(int i=start;i<digits.length();i++){

            int x = digits.charAt(i)-'0';
            String mappedString = mp.get(x);
            for(int j=0;j<mappedString.length();j++){
                comb.append(mappedString.charAt(j));
                backTrack(ans,mp,digits,comb,i+1);
                comb.deleteCharAt(comb.length()-1);
            }
        }
    }
    public List<String> letterCombinations(String digits) {
        
        Map<Integer,String> mp = new HashMap<>();
        mp.put(2,"abc");    mp.put(3,"def");    mp.put(4,"ghi");
        mp.put(5,"jkl");    mp.put(6,"mno");    mp.put(7,"pqrs");
        mp.put(8,"tuv");    mp.put(9,"wxyz");

        List<String> ans = new ArrayList<>();
        if(digits.isEmpty())
            return new ArrayList<>();
        else{
            backTrack(ans,mp,digits,new StringBuilder(),0);
            return ans;
        }
    }
}

Code Complexity

Time Complexity: O(4n)

In the worst case, each digit maps to 4 letters, and we explore all possible combinations.

Space Complexity: O(n)

The space is used for the recursion stack and storing the result, which depends on the input size.

Code copied!