17. Letter Combinations of a Phone Number Leetcode Java

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution:

1. Recursion and backtrack solution

Read the number digit one by one recursively and put the corresponding letter one by one to result string and process the next number digit until the end of the string. Add the result string to the result list.  Then backtrack to last digit and add next letter to result string until all the result strings are captured.

  public List<String> letterCombinations(String digits) {  
     List<String> res=new ArrayList<String>();  
     if(digits==null) return res;  
     String[] pad={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};  
     StringBuilder item=new StringBuilder();  
     helper(0,digits,pad,res,item);  
     return res;  
   }  
   public void helper(int ind,String digits,String[] pad, List<String> res,StringBuilder item){  
     if(ind==digits.length()){  
       res.add(item.toString());  
       return;  
     }  
     String letters=pad[digits.charAt(ind)-'2'];  
     for(int i=0;i<letters.length();i++){  
       item.append(letters.charAt(i));  
       helper(ind+1,digits,pad,res,item);  
       item.deleteCharAt(item.length()-1);  
     }  
   }  

1. Iteration solution
Sometime the interviewer may want you give the both iteration solution and the recursion solution. The iteration solution is to add each letter of the number digit to result list each time processing the new number digit. For example, "23", after the first iteration, the result list would be like{"a","b","c"}, the second iteration for processing "3", will add the corresponding letters to the existing result string in the result list {"ad","bd","cd", "ae","be",...."cf"}

 public List<String> letterCombinations(String digits) {  
    if(digits==null) return null;  
    List<String> res= new ArrayList<String>();  
    res.add("");  
    String[] letters={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};  
    for(int i=0;i<digits.length();i++){  
      String letter=letters[digits.charAt(i)-'2'];  
      List<String> newRes=new ArrayList<String>();  
      for(int j=0; j<letter.length();j++){  
        for(String s: res){  
          s+=letter.charAt(j);  
          newRes.add(s);  
        }  
      }  
      res=newRes;  
    }  
    return res;  
   }