add a solution for 1249

fishercoder1534 · fishercoder1534 · commit 8b08ebf9c8ff · 2021-10-26T15:01:24.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_1249.java b/src/main/java/com/fishercoder/solutions/_1249.java
@@ -1,5 +1,7 @@
 package com.fishercoder.solutions;
 
+import java.util.Deque;
+import java.util.LinkedList;
 import java.util.Stack;
 
 public class _1249 {
@@ -37,4 +39,48 @@ public String minRemoveToMakeValid(String s) {
             return sb.reverse().toString();
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution on 10/26/2021.
+         */
+        public String minRemoveToMakeValid(String s) {
+            Deque<String> stack = new LinkedList<>();
+            int left = 0;
+            int right = 0;
+            for (char c : s.toCharArray()) {
+                if (c == '(') {
+                    stack.addLast(c + "");
+                    left++;
+                } else if (c == ')') {
+                    if (left <= right) {
+                        continue;
+                    } else {
+                        right++;
+                        stack.addLast(c + "");
+                    }
+                } else {
+                    stack.addLast(c + "");
+                }
+            }
+            left = 0;
+            right = 0;
+            StringBuilder sb = new StringBuilder();
+            while (!stack.isEmpty()) {
+                String str = stack.pollLast();
+                if (str.equals(")")) {
+                    right++;
+                    sb.append(str);
+                } else if (str.equals("(")) {
+                    if (right > left) {
+                        sb.append(str);
+                        left++;
+                    }
+                } else {
+                    sb.append(str);
+                }
+            }
+            return sb.reverse().toString();
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_1249Test.java b/src/test/java/com/fishercoder/_1249Test.java
@@ -6,15 +6,18 @@
 
 public class _1249Test {
     private static _1249.Solution1 solution1;
+    private static _1249.Solution2 solution2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _1249.Solution1();
+        solution2 = new _1249.Solution2();
     }
 
     @Test
     public void test1() {
         System.out.println(solution1.minRemoveToMakeValid("lee(t(c)o)de)"));
+        System.out.println(solution2.minRemoveToMakeValid("lee(t(c)o)de)"));
     }
 
     @Test
