Backtrace – leetcode 17 – Letter Combinations of a Phone Number

this is a very classic backtrace problem.

Idea is simple, use ‘call stack’ to store string “a…z”

stack n – z
.
.
stack 1 – a

if stack.length == targetLenth
loop though stack to get char array to string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

 
package com.dw.leetcode;
 
import java.util.*;
 
public class Letter_Combinations_of_a_Phone_Number_17 {
	static final char[][] number = { { 'a', 'b', 'c' }, { 'd', 'e', 'f' }, { 'g', 'h', 'i' }, { 'j', 'k', 'l' },
			{ 'm', 'n', 'o' }, { 'p', 'q', 'r', 's' }, { 't', 'u', 'v' }, { 'w', 'x', 'y', 'z' }
	};
 
    public List<String> letterCombinations(String digits) {
    	List<String> result = new ArrayList<String>();
    	if(digits.length() == 0){
            return new ArrayList<>(); 
        }
 
    	foo(digits, 0, 0, digits.length(), new ArrayList<Character>(), result);
    	return result;
    }
 
    public void foo(String digits, int index, int total, int len, List<Character> temp, List<String> result) {
    	if(total == len) {
    		StringBuilder stringBuilder = new StringBuilder();
    		for(Character c: temp) {
    			stringBuilder.append(c);
    		}
    		result.add(stringBuilder.toString());
    		return;
    	}
 
    	int numberIndex = Integer.parseInt(Character.toString(digits.charAt(index)));
 
    	for(char c: number[numberIndex - 2]) {
    		temp.add(c);
    		foo(digits, index+1, total+1, len, temp, result);
    		temp.remove(temp.size() - 1);
    	}
    }
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Letter_Combinations_of_a_Phone_Number_17 s = new Letter_Combinations_of_a_Phone_Number_17();
		System.out.println(s.letterCombinations("234"));
	}
 
}