add 1002

fishercoder1534 · fishercoder1534 · commit 2d8d7a85228f · 2019-03-04T18:18:38.000-08:00
diff --git a/README.md b/README.md
@@ -27,6 +27,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|1002|[Find Common Characters](https://leetcode.com/problems/find-common-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1002.java) | O(n) | O(1) | |Easy|
 |999|[Available Captures for Rook](https://leetcode.com/problems/available-captures-for-rook/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_999.java) | O(1) | O(1) | |Easy|
 |997|[Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_997.java) | O(n) | O(n) | |Easy| 
 |994|[Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_994.java) | O(m*2*n*2) | O(m*n) | |Easy| BFS
diff --git a/src/main/java/com/fishercoder/solutions/_1002.java b/src/main/java/com/fishercoder/solutions/_1002.java
@@ -0,0 +1,62 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 1002. Find Common Characters
+ *
+ * Given an array A of strings made only from lowercase letters,
+ * return a list of all characters that show up in all strings within the list (including duplicates).
+ * For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.
+ *
+ * You may return the answer in any order.
+ *
+ * Example 1:
+ * Input: ["bella","label","roller"]
+ * Output: ["e","l","l"]
+ *
+ * Example 2:
+ * Input: ["cool","lock","cook"]
+ * Output: ["c","o"]
+ *
+ * Note:
+ *
+ * 1 <= A.length <= 100
+ * 1 <= A[i].length <= 100
+ * A[i][j] is a lowercase letter
+ */
+public class _1002 {
+  public static class Solution1 {
+    public List<String> commonChars(String[] A) {
+      int[][] charCount = new int[A.length][26];
+      for (int i = 0; i < A.length; i++) {
+        for (char c : A[i].toCharArray()) {
+          charCount[i][c - 'a']++;
+        }
+      }
+      List<String> result = new ArrayList<>();
+      for (int i = 0; i < 26; i++) {
+        while (charCount[0][i] != 0) {
+          char c = (char) (i + 'a');
+          boolean valid = true;
+          charCount[0][i]--;
+          for (int j = 1; j < A.length; j++) {
+            if (charCount[j][i] == 0) {
+              valid = false;
+              break;
+            } else {
+              charCount[j][i]--;
+            }
+          }
+          if (!valid) {
+            break;
+          } else {
+            result.add("" + c);
+          }
+        }
+      }
+      return result;
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_1002Test.java b/src/test/java/com/fishercoder/_1002Test.java
@@ -0,0 +1,28 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.CommonUtils;
+import com.fishercoder.solutions._1002;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+public class _1002Test {
+  private static _1002.Solution1 solution1;
+  private static String[] A;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _1002.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    A = new String[] {"bella", "label", "roller"};
+    CommonUtils.print(solution1.commonChars(A));
+  }
+
+  @Test
+  public void test2() {
+    A = new String[] {"cool", "lock", "cook"};
+    CommonUtils.print(solution1.commonChars(A));
+  }
+}
