add 844

fishercoder1534 · fishercoder1534 · commit edd9dcc25f57 · 2018-06-16T17:36:01.000-07:00
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|844|[Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_844.java) | O(n) | O(1) | |Easy|
 |832|[Flipping an Image](https://leetcode.com/problems/flipping-an-image/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_832.java) | O(n) | O(1) | |Easy|
 |830|[Positions of Large Groups](https://leetcode.com/problems/positions-of-large-groups/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_830.java) | O(n) | O(n) | |Easy|
 |824|[Goat Latin](https://leetcode.com/problems/goat-latin/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_824.java) | O(n) | O(1) | |Easy| 
diff --git a/src/main/java/com/fishercoder/solutions/_844.java b/src/main/java/com/fishercoder/solutions/_844.java
@@ -0,0 +1,58 @@
+package com.fishercoder.solutions;
+
+/**
+ * 844. Backspace String Compare
+ *
+ * Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
+ *
+ * Example 1:
+ * Input: S = "ab#c", T = "ad#c"
+ * Output: true
+ * Explanation: Both S and T become "ac".
+ *
+ *  Example 2:
+ * Input: S = "ab##", T = "c#d#"
+ * Output: true
+ * Explanation: Both S and T become "".
+ *
+ *  Example 3:
+ * Input: S = "a##c", T = "#a#c"
+ * Output: true
+ * Explanation: Both S and T become "c".
+ *
+ * Example 4:
+ * Input: S = "a#c", T = "b"
+ * Output: false
+ * Explanation: S becomes "c" while T becomes "b".
+ * Note:
+ *
+ * 1 <= S.length <= 200
+ * 1 <= T.length <= 200
+ * S and T only contain lowercase letters and '#' characters.
+ * Follow up:
+ *
+ * Can you solve it in O(N) time and O(1) space?
+ */
+public class _844 {
+  public static class Solution1 {
+    public boolean backspaceCompare(String S, String T) {
+      String processedS = process(S);
+      String processedT = process(T);
+      return processedS.equals(processedT);
+    }
+
+    private String process(String str) {
+      StringBuilder sb = new StringBuilder();
+      for (int i = 0; i < str.length(); i++) {
+        if (str.charAt(i) == '#') {
+          if (sb.length() > 0) {
+            sb.deleteCharAt(sb.length() - 1);
+          }
+        } else {
+          sb.append(str.charAt(i));
+        }
+      }
+      return sb.reverse().toString();
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_844Test.java b/src/test/java/com/fishercoder/_844Test.java
@@ -0,0 +1,37 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._844;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _844Test {
+  private static _844.Solution1 solution1;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _844.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    assertEquals(true, solution1.backspaceCompare("ab#c", "ad#c"));
+  }
+
+  @Test
+  public void test2() {
+    assertEquals(true, solution1.backspaceCompare("ab##", "c#d#"));
+  }
+
+  @Test
+  public void test3() {
+    assertEquals(true, solution1.backspaceCompare("a##c", "#a#c"));
+  }
+
+  @Test
+  public void test4() {
+    assertEquals(false, solution1.backspaceCompare("a#c", "b"));
+  }
+
+}
