Counting ambiguous Morse Code encodings, with and without Java Streams

Question

Unique Morse Code Words

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cab" can be written as "-.-.-....-", (which is the concatenation "-.-." + "-..." + ".-"). We'll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example:

Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation:
The transformation of each word is:

• "gin" → "--...-."
• "zen" → "--...-."
• "gig" → "--...--."
• "msg" → "--...--."

There are 2 different transformations, "--...-." and "--...--.".

Note:

• The length of words will be at most 100.
• Each words[i] will have length in range [1, 12].
• words[i] will only consist of lowercase letters.

My approach:

import java.util.*;

    class Solution {
        public int uniqueMorseRepresentations(String[] words) {

            HashMap<String,String> morseMap = new HashMap<>(26);
                       String [] morseWords = new String[] {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

        HashSet<String> uniqCode = new HashSet<>();
        String morse = "";
        int ind;

        for( int i = 0; i < words.length; i++ )
        {
            morse = "";
            for( int j = 0; j < words[i].length(); j++ )
            {
                ind = ((int)words[i].charAt(j)) - 97;
                morse += morseWords[ind];
            }
            uniqCode.add(morse);
        }

            return uniqCode.size();

        }
    }

A 2nd approach using Java Stream:

public int uniqueMorseRepresentations(String[] words) {
        Set<String> res = Arrays.stream(words).map(i -> getMC(i)).collect(Collectors.toSet());
        return res.size();
    }
    private String getMC(String str) {
        String[] mCode = {".-","-...","-.-.","-..",".","..-.","--.","....","..",
                          ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
                          "...","-","..-","...-",".--","-..-","-.--","--.."};
        return str.chars().mapToObj(ch -> mCode[(char)ch % 97]).reduce("", String::concat);
    }

With regards to the above code snippets, I have the following questions:

1. Which approach is better according to an interviewer?

2. What can be improved in the 1st approach?

3. Does the 2nd approach sacrifice readability for succintness?

4. Is there a better method, eg StringBuilder in place of string that can speed up the solution of the first approach?

Answer 1

Well, I do not want to be the one always hammering on using Streams, but your second solution was almost immediatly clear to me, whereas the first was not. It does help that with the second one you split it up into methods, a very good thing!

Nontheless, I still think you can improve the second solution:

• First, I would save the morse code mapping in a field, as it is really a constant thing.
• Second, collecting to a Set is not really necessary. A Stream has a count method, so you can use that. Of course, this will result in a wrong answer, because we only want to count the distinct number of morse code strings. How do we solve it? Call distinct first!
• There is really no reason to shorten method names, nor variables. Use clear, useful names. Instead of getMC, use toMorseCode for example.
• In this particular case, I think there is a slightly better way to calculate the index out of a character, namely subtracting with 'a', which also has an integer value of 97 but now I think it is perfectly clear what is happening, i.e. 'a' = 0, 'b' = 1, ....

Putting it all together, with a method reference here and a static import there:

import static java.util.Arrays.stream;
import static java.util.stream.Collectors.joining;

public final class Morse {

    private static final String[] CODE_TABLE = {
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
            ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.",
            "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
    };

    public static long countUniqueMorseRepresentations(final String[] words) {
        return stream(words).map(Morse::toMorseCode).distinct().count();
    }

    private static String toMorseCode(final String string) {
        return string.chars().mapToObj(character -> CODE_TABLE[character - 'a']).collect(joining(""));
    }
}

A short comment about your first approach, using a StringBuilder would be a good thing, because concatenating Strings with + each time builds a new String object, whereas with a StringBuilder, you would only make a new String when you concatenated all parts.

In this very case though, pure performance wise, it might get optimized under the hood to use a StringBuilder anyway.

Answer 2

I'm going to skip commenting on the streaming approach because @Koekje has it covered. As far as the non-streaming approach:

• morseMap is unused and should be removed

• morseWords should be a class variable. The name is also wrong. It's not words, it's the character encoding.

• morse should be a StringBuilder, and it should be declared inside the loop. Always constrain variables as tightly as possible. Also, the problem statement told you that it should be called transformation.

• ind is a terrible name and the variable doesn't serve any real purpose.

• Using enhanced for loops would make it a lot easier to read.

• uniqCode - there's no charge for spelling out uniqueCodes. Also, they're not codes, they're transformations. The fact that it's a Set makes the unique part implicit.

As for the questions:

1. We have no way of knowing what an interviewer would like to see. Frankly, if you're inexperienced, I'd rather see the first (can you write code?), and if you're experienced I'd rather see the second (have you learned the stream API?).

2. See above.

3. See @Koekje's answer.

4. Any reasonable compiler will swap out your string concatenation for a StringBuilder behind the scenes. The only reliable way to find performance problems is through testing in a real-world environment.

If I were to rewrite your code considering my observations above, it might look something like:

class Solution {

    private static final String[] MORSE_ENCODING = new String[] {
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--",
            "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." 
    };

    public int uniqueMorseRepresentations(final String[] words) {
        final Set<String> transformations = new HashSet<>();
        for (final String word : words) {
            final StringBuilder transformation = new StringBuilder();
            for (final char character : word.toCharArray()) {
                transformation.append(MORSE_ENCODING[character - 'a']);
            }
            transformations.add(transformation.toString());
        }
        return transformations.size();
    }
}