SkyDC SkyDC - 8 days ago 5
Java Question

Recursive list mnemonics

I am working on a project to pass in a 3 digit String and it should return an ArrayList of all possible mnemonic combinations. For example, if I pass in the digits "623", it should return a list of
[MAD MBD MCD NAD NBD NCD OAD OBD OCD
MAE MBE MCE NAE NBE NCE OAE OBE OCE
MAF MBF MCF NAF NBF NCF OAF OBF OCF].

However, I keep getting a result of [MAD, MADE, MADEF, MABD, MABDE, MABDEF, MABCD, MABCDE, MABCDEF, MNAD, MNADE, MNADEF, MNABD, MNABDE, MNABDEF, MNABCD, MNABCDE, MNABCDEF, MNOAD, MNOADE, MNOADEF, MNOABD, MNOABDE, MNOABDEF, MNOABCD, MNOABCDE, MNOABCDEF]. I can't seem to figure out what I am doing wrong here.. It's supposed to return Strings of length 3 and it just appears to tack on the previous letters.

Here is my code:

public class PhoneMnemonics {
public static void main(String[] args) {
ArrayList<String> test = listMnemonics("623");
System.out.print(test);
}

public static ArrayList<String> listMnemonics(String number) {
ArrayList<String> result = new ArrayList<String>();
recursiveMnemonics(result, "", number);
return result;
}

private static void recursiveMnemonics(ArrayList<String> result, String mnemonicSoFar, String digitsLeft) {
if (digitsLeft.length() == 0) {
// Add current mnemonic
result.add(mnemonicSoFar);
} else {
// Try all combinations for single digit
int numLetters = digitLetters(digitsLeft.charAt(0)).length();
String letters = digitLetters(digitsLeft.charAt(0));
if (digitsLeft.length() > 1 ) {
digitsLeft = digitsLeft.substring(1);
} else {
digitsLeft = "";
}
for (int i = 0; i < numLetters; i++) {
char c = letters.charAt(i);
mnemonicSoFar = mnemonicSoFar + Character.toString(c);
recursiveMnemonics(result, mnemonicSoFar, digitsLeft);
}
}
}

public static String digitLetters(char ch) {
String result = "";
switch (ch) {
case '2': result = "ABC";
break;
case '3': result = "DEF";
break;
case '4': result = "GHI";
break;
case '5': result = "JKL";
break;
case '6': result = "MNO";
break;
case '7': result = "PQRS";
break;
case '8': result = "TUV";
break;
case '9': result = "WXYZ";
break;
}
return result;
}
}


Any help is much appreciated!

EDIT: I moved the if statement which edits the digitsLeft string higher in the code and it modified my results a bit.

Answer

The main problem is that mnemonicSoFar should be fixed after you add it to the results. For example:

You reach MAD and you add it to the result. After that you need to to the same thing with mnemonicSoFar = MA and the letter to be added E. Notice that you take the the last letter of mnemonicSoFar out. So you should correct your code to this:

for (int i = 0; i < numLetters; i++) {
                char c = letters.charAt(i);
                mnemonicSoFar = mnemonicSoFar + Character.toString(c);
                recursiveMnemonics2(result, mnemonicSoFar, digitsLeft);
                mnemonicSoFar = mnemonicSoFar.substring(0,mnemonicSoFar.length()-1); 
}

If you care to improve your coding style, I refactored your code a bit.

private static void recursiveMnemonics(ArrayList<String> result, String mnemonicSoFar, String digitsLeft) {
   if(digitsLeft.length() == 0) {
       result.add(mnemonicSoFar);
       return;
   }
   String letters = digitLetters(digitsLeft.charAt(0));
   digitsLeft = digitsLeft.substring(1);
   for(int i = 0; i < letters.length(); i++) {
      mnemonicSoFar = mnemonicSoFar + letters.charAt(i);
      recursiveMnemonics(result, mnemonicSoFar, digitsLeft);
      mnemonicSoFar = mnemonicSoFar.substring(0,mnemonicSoFar.length()-1);
   }
}

In my opinion it is much more readable.