Decode ambiguous Morse code

Question

Stumbled upon this interview question:

Given a morse encoded sentence with no spaces or separation between letters or words and a list of words contained in the message, decode it.

This was my solution (and a test case with the jack and jill sentence):

 static String[] alpha = {"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"};
static String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",
        ".--","-..-","-.--","--.."};

private static HashMap<Character, String> letters = new HashMap<>();

public static void main(String[] args) {
    for (int i = 0; i < alpha.length; i++) {
        letters.put(alpha[i].charAt(0), morse[i]);
    }

    String[] words = {"hill","jack","went","and","jill","the","up"};
    System.out.println(
            decode(".---.--.-.-.-.--.-...---...-...-...--.-.-..-.--.-............-...-..",
                    words)
    );
}

private static String decode(String code, String[] words){
    String[] encodedWords = new String[words.length];
    for (int i = 0; i < words.length; i++) {
        encodedWords[i] = encodeWord(words[i]);
    }

    return decodePossibility(code, words, encodedWords, new StringBuilder());
}

private static String decodePossibility(String code, String[] words, String[] encodedWords, StringBuilder current){
    if(code.length() == 0) return current.toString();
    for (int i = 0; i < encodedWords.length; i++) {
        if(code.length() >= encodedWords[i].length()){
            if(code.substring(0, encodedWords[i].length()).equals(encodedWords[i])){
                String result = decodePossibility(code.substring(encodedWords[i].length()), words, encodedWords, current.append(words[i]).append(' '));
                if(result != null){
                    return result;
                }
            }
        }
    }
    return null;
}

private static String encodeWord(String word){
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < word.length(); i++) {
        stringBuilder.append(letters.get(word.charAt(i)));
    }
    return stringBuilder.toString();
}

Any tips on how to improve the code? Any alternative solution? To back track to a correct solution I would prefer throwing an exception, but sadly I'am not allowed to do so.

Answer 1

White Space

This is hard on my aging eyes:

static String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",
    ".--","-..-","-.--","--.."};

This is much easier to read:

static String[] morse = {
    ".-",   "-...",  "-.-.",  "-..",   ".",     "..-.",  "--.",   "....",  "..",   ".---",
    "-.-",  ".-..",  "--",    "-.",    "---",   ".--.",  "--.-",  ".-.",   "...",  "-",
    "..-",  "...-",  ".--",   "-..-",  "-.--",  "--.."
};

alpha[i].charAt(0)

In the following, you use create 26 strings, and call .charAt(0) on each:

static String[] alpha = {"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"};
static String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",
    ".--","-..-","-.--","--.."};

private static HashMap<Character, String> letters = new HashMap<>();

public static void main(String[] args) {
    for (int i = 0; i < alpha.length; i++) {
        letters.put(alpha[i].charAt(0), morse[i]);
    }

You could simply use one 26-character string:

final static String alpha = "abcdefghijklmnopqrstuvwxyz";

...

for (int i = 0; i < alpha.length(); i++) {
    letters.put(alpha.charAt(i), morse[i]);
}

Or you could statically initialize the structure directly:

Map<Character, String> letters = Map.of(
    'a', ".-",    'b', "-...",  'c', "-.-.",  'd', "-..",  'e', ".",
    'f', "..-.",  'g', "--.",   'h', "....",  'i', "..",   'j', ".---",
    ... etc ...);

Stream API

The following code:

private static String encodeWord(String word){
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < word.length(); i++) {
        stringBuilder.append(letters.get(word.charAt(i)));
    }
    return stringBuilder.toString();
}

is pretty straight forward. It could be reduced to 1 line of code with the Stream API, if you are familiar with it:

private static String encodeWord(String word){
    return word.chars().mapToObj(i -> letters.get((char) i).collect(Collectors.joining());
}

Words & Encoded Words

Right now, you are allocating a parallel array for encodedWords, and matching words and encoded words by index. You could merge these two structures into one object, a Map<String, String> where encoded words map to their decoded values. Passing this object to decodePossibility would be more cohesive than two arrays, which could be of different length.

Efficiency

Continuing with the Map<String, String> of decodings...

In decodePossibility, you are looping over all encodedWords trying each one to see if it is the next possibility in the message. With 7 words, this isn't too inefficient, but if the list of words was larger, it could be.

Instead, you could find the length of the shortest encoded word, and develop a Map of lists of words starting with a prefixes of that length:

Map<String, Map<String, String>> partitioned_decoding;

For instance, the encoding of "the" produces the shortest sequence -..... of 6 characters, so in partition_decoding each key would be the first 6 characters of encodedWords, and each value would contain a mapping of encodedWords to words for only the encodedWords starting with that key.

"-....."  ->  Map.of("-.....", "the")
".---.-"  ->  Map.of(".---.--.-.-.-", "jack")
".---.."  ->  Map.of(".---...-...-..", "jill")
".--.-."  ->  Map.of(".--.-.-", "went", ".--.-..", "and")
"..-.--"  ->  Map.of("..-.--.", "up")
"......"  ->  Map.of(".......-...-..", "hill")

During decodePossibility, if code was at least 6 characters long, you would fetch the first 6 characters of code, look up that entry in partitioned_decoding, and if present, loop over that (ideally only 1) entry in that submap. In the case of ".--.-.", you'd have to try both "went" and "and", but that is only 2 words, which is still much smaller than examining all 7.

Neither "e" or "t" are valid single letter words, so the worst case would be if words contained the word "a", which would cause the key length to reduce to 2 characters, and words would be partitioned into 4 different bins: "--", ".-", "-.", and "..", which should still provide a 4 times speed-up, since only one quarter of entries would be checked at each stage.

Alternative to Recursion

Instead of recursion, you could use a loop, and allocate your own stacks for current position and word iteration for each level. When a solution is found, the return statement would directly return the solution - no need to check for a sub-step returning non-null and returning that value, eventually unwinding the call-stack to the top. When a dead-end is found, you pop the previous state from your own stacks, and continue looping until a solution is found or no solution is possible.