My recursive solution using Java


  • 50
    L
       public class Solution {
        	private static final String[] KEYS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        
        	public List<String> letterCombinations(String digits) {
        		List<String> ret = new LinkedList<String>();
        		combination("", digits, 0, ret);
        		return ret;
        	}
        
        	private void combination(String prefix, String digits, int offset, List<String> ret) {
        		if (offset >= digits.length()) {
        			ret.add(prefix);
        			return;
        		}
        		String letters = KEYS[(digits.charAt(offset) - '0')];
        		for (int i = 0; i < letters.length(); i++) {
        			combination(prefix + letters.charAt(i), digits, offset + 1, ret);
        		}
        	}
        }

  • 3
    F

    make "prefix" variable a StringBuilder type might be even better.


  • 13

    Hey bro, I tested your code. To pass the "" case, you need to include

    if(digits == null || digits.length() == 0) return ret;
    

    It should return []. But your code will wrongly return [""].


  • 0
    L

    Thanks for pointing it out.


  • 0
    A

    @fsr0023120 wont work. since stringbuilders in java have same object and reference. whereas for string a same refrence exists but a new object is created


  • 0
    Z

    @akamUSC I think using a stringbuilder will be ok with the problem you said, because when we call stringbuilder.tostring(), it will create a new string object, then you can add it into the list. But I encounter another problem about indexoutofbound for stringbuilder and I cannot figure out what caused it so I change back to use string in my own solution.


  • 5

    @akamUSC @zhangruoxi To use StringBuilder instead, in additional to changing all the function signatures, simply record the the sb length before the recursive call, and change the sb length back after it returns. Just 2 additional lines inside the for loop.

    You can also refer to this thread

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) return res;
        StringBuilder sb = new StringBuilder();
        combine(res, digits, sb, 0);
        return res;
    }
    
    private void combine(List<String> res, String digits, StringBuilder sb, int posn) {
        if (posn == digits.length()) {
            res.add(sb.toString());
            return;
        }
        String letters = KEYS[digits.charAt(posn) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            int sbLen = sb.length();
            combine(res, digits, sb.append(letters.charAt(i)), posn+1);
            sb.setLength(sbLen);
        }
    }
    

  • 0
    R

    @lei31 What will be the time complexity? I am thinking k * (2^n)
    where k = average length of string in KEYS and n is the length of digits.
    Thanks in adv !!


  • 6
    C

    @ranhar Well, I think it will be k^n


  • 1

    Similar solution with StringBuilder and ArrayList instead:

    private static final String[] LETTERS = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) { 
      return (digits.length() == 0) ? Arrays.asList()
                                    : permute(digits, new StringBuilder(), new ArrayList<>(), 0); 
    } 
    private List<String> permute(String digits, StringBuilder result, List<String> results, int i) {
      if (i == digits.length()) results.add(result.toString());
      else for (char c : LETTERS[Character.digit(digits.charAt(i), 10)].toCharArray()) {
             result.append(c);
             permute(digits, result, results, i + 1);
             result.deleteCharAt(result.length() - 1);
           }
      return results;
    }
    

  • 0

    @fsr0023120 hi bro, I tried with "prefix" a StringBuilder type, and the answer is not correct. Because String is a const while StringBuilder causes a reference-pass during the recursive. So if input "abc" it turns out "a", "ab" and "abc".


  • 0
    S

    Thank you for your solution! By the way, what's the time complexity? 3^N?


  • 0
    A

    I like the solution, thanks. Does it satisfies time requirement? How many milliseconds does it require?


  • 0

    If you prefer a single recursive function, here is an alternate solution:

    public List<String> letterCombinations(String digits) {
    	String map[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    
    	List<String> ans = new ArrayList<String>();
    	if (digits.isEmpty()) return ans;
    
    	List<String> ansForSuffix = new ArrayList<String>();
    	if (digits.length() == 1) ansForSuffix.add("");
    	else ansForSuffix = letterCombinations(digits.substring(1));
    
    	for ( String s: ansForSuffix)
    	    for (char c: map[Character.getNumericValue(digits.charAt(0))].toCharArray())
    		ans.add(c + s);
    	return ans;
    } 
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.