Letter Combinations

Medium

Python

def letter_combinations(digits):
    if not digits: return []
    phone={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    res=[]
    def bt(i,path):
        if i==len(digits): res.append(path); return
        for c in phone[digits[i]]: bt(i+1,path+c)
    bt(0,'')
    return res

Java

public List<String> letterCombinations(String digits){
    if(digits.isEmpty()) return new ArrayList<>();
    String[] phone={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> res=new ArrayList<>();
    backtrack(digits,phone,res,0,new StringBuilder());
    return res;
}
void backtrack(String d,String[] p,List<String> res,int i,StringBuilder path){
    if(i==d.length()){res.add(path.toString());return;}
    for(char c:p[d.charAt(i)-'2'].toCharArray()){
        path.append(c);
        backtrack(d,p,res,i+1,path);
        path.deleteCharAt(path.length()-1);
    }
}

Key Insight

Python dict for phone vs Java array indexed by digit-'2'. String immutability vs StringBuilder.

Python → Java Differences

Python dict vs Java array
path+c immutable vs StringBuilder
Backtracking structure identical

Python

def letter_combinations(digits):
    if not digits: return []
    phone={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    res=[]
    def bt(i,path):
        if i==len(digits): res.append(path); return
        for c in phone[digits[i]]: bt(i+1,path+c)
    bt(0,'')
    return res

Java

public List<String> letterCombinations(String digits){
    if(digits.isEmpty()) return new ArrayList<>();
    String[] phone={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> res=new ArrayList<>();
    backtrack(digits,phone,res,0,new StringBuilder());
    return res;
}
void backtrack(String d,String[] p,List<String> res,int i,StringBuilder path){
    if(i==d.length()){res.add(path.toString());return;}
    for(char c:p[d.charAt(i)-'2'].toCharArray()){
        path.append(c);
        backtrack(d,p,res,i+1,path);
        path.deleteCharAt(path.length()-1);
    }
}

Algorithm Steps

1. For each digit try each letter
2. Recurse to next
3. Collect complete paths

← Previous All Backtracking Next →