add 804

fishercoder1534 · fishercoder1534 · commit 2369fcc8a6a6 · 2018-03-28T07:53:45.000-07:00
diff --git a/README.md b/README.md
@@ -23,6 +23,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
 |806|[Number of Lines To Write String](https://leetcode.com/problems/number-of-lines-to-write-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_806.java) | O(n) | O(1) | |Easy|
+|804|[Unique Morse Code Words](https://leetcode.com/problems/unique-morse-code-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_804.java) | O(S) | O(S) | |Easy|
 |799|[Champagne Tower](https://leetcode.com/problems/champagne-tower/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_799.java) | O(r^2) or O(1) | O(r^2) or O(1) | |Medium|
 |796|[Rotate String](https://leetcode.com/problems/rotate-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_796.java) | O(n) | O(1) | |Easy|
 |791|[Custom Sort String](https://leetcode.com/problems/custom-sort-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_791.java) | O(n+m) | O(1) | |Medium|
diff --git a/src/main/java/com/fishercoder/solutions/_804.java b/src/main/java/com/fishercoder/solutions/_804.java
@@ -0,0 +1,55 @@
+package com.fishercoder.solutions;
+
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * 804. 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.
+ */
+public class _804 {
+  public static class Solution1 {
+    public int uniqueMorseRepresentations(String[] words) {
+      String[] morseCodes =
+          new String[] {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
+              "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-",
+              ".--", "-..-", "-.--", "--.."};
+      Set<String> concatenation = new HashSet<>();
+      StringBuilder sb = new StringBuilder();
+      for (String word : words) {
+        sb.setLength(0);
+        for (char c : word.toCharArray()) {
+          sb.append(morseCodes[c - 'a']);
+        }
+        concatenation.add(sb.toString());
+      }
+      return concatenation.size();
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_804Test.java b/src/test/java/com/fishercoder/_804Test.java
@@ -0,0 +1,23 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._804;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _804Test {
+  private static _804.Solution1 solution1;
+  private static String[] words;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _804.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    words = new String[] {"gin", "zen", "gig", "msg"};
+    assertEquals(2, solution1.uniqueMorseRepresentations(words));
+  }
+}
