add 944

fishercoder1534 · fishercoder1534 · commit 74bdd8293695 · 2018-12-19T08:36:27.000-08:00
diff --git a/README.md b/README.md
@@ -29,6 +29,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|944|[Delete Columns to Make Sorted](https://leetcode.com/problems/delete-columns-to-make-sorted/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_944.java) | O(n) | O(1) | |Easy|
 |941|[Valid Mountain Array](https://leetcode.com/problems/valid-mountain-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_941.java) | O(n) | O(1) | |Easy|
 |933|[Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_933.java) | O(n) | O(n) | |Easy|
 |929|[Unique Email Addresses](https://leetcode.com/problems/unique-email-addresses/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_929.java) | O(n) | O(n) | |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_944.java b/src/main/java/com/fishercoder/solutions/_944.java
@@ -0,0 +1,58 @@
+package com.fishercoder.solutions;
+
+/**
+ * 944. Delete Columns to Make Sorted
+ *
+ * We are given an array A of N lowercase letter strings, all of the same length.
+ * Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
+ * For example, if we have an array A = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3},
+ * then the final array after deletions is ["bef", "vyz"], and the remaining columns of A are ["b","v"], ["e","y"],
+ * and ["f","z"].  (Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]].)
+ *
+ * Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.
+ *
+ * Return the minimum possible value of D.length.
+ *
+ * Example 1:
+ *
+ * Input: ["cba","daf","ghi"]
+ * Output: 1
+ * Explanation:
+ * After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
+ * If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.
+ * Example 2:
+ *
+ * Input: ["a","b"]
+ * Output: 0
+ * Explanation: D = {}
+ * Example 3:
+ *
+ * Input: ["zyx","wvu","tsr"]
+ * Output: 3
+ * Explanation: D = {0, 1, 2}
+ *
+ *
+ * Note:
+ *
+ * 1 <= A.length <= 100
+ * 1 <= A[i].length <= 1000
+ * */
+public class _944 {
+  public static class Solution1 {
+    public int minDeletionSize(String[] A) {
+      if (A == null || A.length == 0) {
+        return 0;
+      }
+      int deletion = 0;
+      for (int i = 0; i < A[0].length(); i++) {
+        for (int j = 0; j < A.length - 1; j++) {
+          if (A[j].charAt(i) > A[j + 1].charAt(i)) {
+            deletion++;
+            break;
+          }
+        }
+      }
+      return deletion;
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_944Test.java b/src/test/java/com/fishercoder/_944Test.java
@@ -0,0 +1,35 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._944;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static junit.framework.Assert.assertEquals;
+
+public class _944Test {
+  private static _944.Solution1 solution1;
+  private static String[] A;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _944.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    A = new String[] {"cba", "daf", "ghi"};
+    assertEquals(1, solution1.minDeletionSize(A));
+  }
+
+  @Test
+  public void test2() {
+    A = new String[] {"a", "b"};
+    assertEquals(0, solution1.minDeletionSize(A));
+  }
+
+  @Test
+  public void test3() {
+    A = new String[] {"zyx", "wvu", "tsr"};
+    assertEquals(3, solution1.minDeletionSize(A));
+  }
+}
