6
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Thanks, @200_success for the edits. I will try to make my questions more specific from next time. \$\endgroup\$ – Anirudh Thatipelli May 5 '18 at 5:30
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks, @Koekje for your valuable advice. I had observed that using StringBuilder in place of String improved the runtime by almost 2 milliseconds. I wasn't sure how it was happening but your answer \$\endgroup\$ – Anirudh Thatipelli May 5 '18 at 5:39
  • \$\begingroup\$ A naive question, how does writing import static differ from writing only import. \$\endgroup\$ – Anirudh Thatipelli May 5 '18 at 5:51
  • \$\begingroup\$ @AnirudhThatipelli note that it is not trivial to do correct performance measures, it is a whole different beast all together. I highly doubt that the 2ms difference you observe is due to using the StringBuilder yourself. (again note, the String concatentation in your case is highly likely to compile to somewhat the same) \$\endgroup\$ – Koekje May 5 '18 at 9:46
  • \$\begingroup\$ @AnirudhThatipelli the difference is that with static imports you import static methods and static fields, whereas with a normal import, you import classes. Static imports allow you to use the methods and fields without fully qualifying them, like here e.g. joining("") instead of Collectors.joining(""). Do not that it can in fact make the code more difficult to read, so use it sparingly, where it really improves the code (for me, in the usage of Streams for example). Also, you should probably never static import all with *, it pollutes the namespace and makes everything hard to track. \$\endgroup\$ – Koekje May 5 '18 at 9:49
5
\$\begingroup\$

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();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks, @Eric Stein for your suggestions. On the Leetcode's website, the solution using StringBuilder was taking 2 milliseconds less than its String counterpart. \$\endgroup\$ – Anirudh Thatipelli May 5 '18 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.