leetcode

commit 8561c37ee0c619ca1b21fbce159c647ae2739b2d
parent 561d8cfd2522570c9953965b97b4da4e25841f49
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 11 Apr 2023 09:52:19 +0200

Daily Problem

Diffstat:
M
Problems/2390.cpp
 | 
36
++++++++++++++++++++++++++++++++++++

1 file changed, 36 insertions(+), 0 deletions(-)
diff --git a/Problems/2390.cpp b/Problems/2390.cpp
@@ -1,3 +1,4 @@
+// Stack solution
 class Solution {
 public:
   string removeStars(string s) {
@@ -17,3 +18,38 @@ public:
     return res;
   }
 };
+
+// Deque solution, avoid reversal
+class Solution {
+public:
+  string removeStars(string s) {
+    deque<char> dq;
+    for (const char &c : s)
+      if (c == '*')
+        dq.pop_back();
+      else
+        dq.push_back(c);
+
+    string res = "";
+    while (!dq.empty()) {
+      res += dq.front();
+      dq.pop_front();
+    }
+    return res;
+  }
+};
+
+// Two pointer, constant space, solution
+class Solution {
+public:
+  string removeStars(string s) {
+    int i = 0;
+    for (int j = 0; j < s.size(); j++) {
+      if (s[j] == '*')
+        i--;
+      else
+        s[i++] = s[j];
+    }
+    return s.substr(0, i);
+  }
+};