2390.cpp (1143B)
1 // Stack solution 2 class Solution { 3 public: 4 string removeStars(string s) { 5 stack<char> st; 6 for (char c : s) 7 if (c == '*') 8 st.pop(); 9 else 10 st.push(c); 11 12 string res = ""; 13 while (!st.empty()) { 14 res += st.top(); 15 st.pop(); 16 } 17 reverse(res.begin(), res.end()); 18 return res; 19 } 20 }; 21 22 // Deque solution, avoid reversal 23 class Solution { 24 public: 25 string removeStars(string s) { 26 deque<char> dq; 27 for (const char &c : s) 28 if (c == '*') 29 dq.pop_back(); 30 else 31 dq.push_back(c); 32 33 string res = ""; 34 while (!dq.empty()) { 35 res += dq.front(); 36 dq.pop_front(); 37 } 38 return res; 39 } 40 }; 41 42 // Two pointer, constant space, solution 43 class Solution { 44 public: 45 string removeStars(string s) { 46 int i = 0; 47 for (int j = 0; j < s.size(); j++) { 48 if (s[j] == '*') 49 i--; 50 else 51 s[i++] = s[j]; 52 } 53 return s.substr(0, i); 54 } 55 };