find all possible words based on phone numbers

This is a classic code problem:

http://www.geeksforgeeks.org/find-possible-words-phone-digits/

This can be done beautifully in a recursion approach. The key here is to loop through all digits in the phone number from left to right, set the corresponding char in the word based on the phone keyboard, the recursion will terminate when the last digit is passed.

	private final static Map<Integer, char[]> store = new HashMap<>();
	static {
	store.put(1, new char[]{'1'});
	store.put(2, new char[]{'A', 'B', 'C'});
	store.put(3, new char[]{'D', 'E', 'F'});
	store.put(4, new char[]{'G', 'H', 'I'});
	store.put(5, new char[]{'J', 'K', 'L'});
	store.put(6, new char[]{'M', 'N', 'O'});
	store.put(7, new char[]{'P', 'R', 'Q', 'S'});
	}
	public static void phoneNum2String(int[] phone){
	char[] curr = new char[phone.length];
	phoneNum2StringRec(phone, 0, curr);
	}
	private static void phoneNum2StringRec(int[] phone, int index, char[] curr){
	int len = phone.length;
	if(index==len)
	System.out.println(curr);
	else{
	char[] chars = store.get(phone[index]);
	for(char c : chars){
	curr[index] = c;
	phoneNum2StringRec(phone, index+1, curr);
	}
	}
	}

view raw phoneNum2String hosted with ❤ by GitHub

Another approach is to do it iterativelly. The key here is to find a way to calculate next word from a current word. for example, if the current word is ADG, then next word is ADH, next after that is ADI, AEG.

	public static void phoneNum2StringIter(int[] phone){
	int len = phone.length;
	char[] curr = new char[phone.length];
	for(int i=0;i<phone.length; i++)
	curr[i] = store.get(phone[i])[0];
	System.out.println(curr);
	while(findNext(phone, curr)){
	System.out.println(curr);
	}
	}
	private static boolean findNext(int[] phone, char[] curr){
	//we loop through from right
	for(int i=phone.length-1;i>=0;i--){
	char[] chars = store.get(phone[i]);
	int found = -1;
	for(int index = 0; index<chars.length; index++)
	if(chars[index] == curr[i])
	found = index;
	if(found!=-1 && found+1<chars.length){
	//we find the index of curr[i] and set it to next char
	curr[i] = chars[found+1];
	//also set all of the chars to its right to mimimum values
	for(int j=i+1;j<phone.length;j++){
	curr[j] = store.get(phone[j])[0];
	}
	return true;
	}
	}
	return false;
	}

view raw phoneNum2StringIter.java hosted with ❤ by GitHub