add 838

fishercoder1534 · fishercoder1534 · commit cf8de87235a3 · 2020-11-27T09:17:33.000-08:00
diff --git a/README.md b/README.md
@@ -350,6 +350,7 @@ _If you like this project, please leave me a star._ &#9733;
 |844|[Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_844.java) | |Easy|
 |841|[Keys and Rooms](https://leetcode.com/problems/keys-and-rooms/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_841.java) |  |Easy|DFS, Graph
 |840|[Magic Squares In Grid](https://leetcode.com/problems/magic-squares-in-grid/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_840.java) |  |Easy|
+|838|[Push Dominoes](https://leetcode.com/problems/push-dominoes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_838.java) | |Medium| Two Pointers, DP
 |836|[Rectangle Overlap](https://leetcode.com/problems/rectangle-overlap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_836.java) | [:tv:](https://youtu.be/o6hHUk4DOW0) |Easy|
 |832|[Flipping an Image](https://leetcode.com/problems/flipping-an-image/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_832.java) |  |Easy|
 |830|[Positions of Large Groups](https://leetcode.com/problems/positions-of-large-groups/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_830.java) |  |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_838.java b/src/main/java/com/fishercoder/solutions/_838.java
@@ -0,0 +1,41 @@
+package com.fishercoder.solutions;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public class _838 {
+    public static class Solution1 {
+        public String pushDominoes(String dominoes) {
+            StringBuilder currentSb = new StringBuilder(dominoes);
+            Set<String> visited = new HashSet<>();
+            visited.add(dominoes);
+            do {
+                StringBuilder newSb = new StringBuilder();
+                for (int i = 0; i < currentSb.length(); i++) {
+                    if (currentSb.charAt(i) == 'L') {
+                        newSb.append('L');
+                        if (i == 1 && currentSb.charAt(i - 1) == '.') {
+                            newSb.replace(i - 1, i, "L");
+                        } else if (i > 1 && currentSb.charAt(i - 1) == '.' && currentSb.charAt(i - 2) != 'R') {
+                            newSb.replace(i - 1, i, "L");
+                        }
+                    } else if (currentSb.charAt(i) == 'R') {
+                        newSb.append('R');
+                        if (i == currentSb.length() - 2 && currentSb.charAt(i + 1) == '.') {
+                            newSb.replace(i + 1, i + 2, "R");
+                            i++;
+                        } else if (i < currentSb.length() - 2 && currentSb.charAt(i + 1) == '.' && currentSb.charAt(i + 2) != 'L') {
+                            newSb.replace(i + 1, i + 2, "R");
+                            i++;
+                        }
+                    } else {
+                        newSb.append('.');
+                    }
+                }
+                currentSb.setLength(0);
+                currentSb = newSb;
+            } while (visited.add(currentSb.toString()));
+            return currentSb.toString();
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_838Test.java b/src/test/java/com/fishercoder/_838Test.java
@@ -0,0 +1,42 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._838;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _838Test {
+    private static _838.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _838.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals("LL.RR.LLRRLL..", solution1.pushDominoes(".L.R...LR..L.."));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals("RR.L", solution1.pushDominoes("RR.L"));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(".", solution1.pushDominoes("."));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals("..RRR", solution1.pushDominoes("..R.."));
+    }
+
+    @Test
+    public void test5() {
+        assertEquals("RRR.L", solution1.pushDominoes("R.R.L"));
+    }
+
+}
