leetcode

0 // Stack solution

1 class Solution {

2 public:

3 string removeStars(string s) {

4 stack<char> st;

5 for (char c : s)

6 if (c == '*')

7 st.pop();

8 else

9 st.push(c);

10

11 string res = "";

12 while (!st.empty()) {

13 res += st.top();

14 st.pop();

15 }

16 reverse(res.begin(), res.end());

17 return res;

18 }

19 };

20

21 // Deque solution, avoid reversal

22 class Solution {

23 public:

24 string removeStars(string s) {

25 deque<char> dq;

26 for (const char &c : s)

27 if (c == '*')

28 dq.pop_back();

29 else

30 dq.push_back(c);

31

32 string res = "";

33 while (!dq.empty()) {

34 res += dq.front();

35 dq.pop_front();

36 }

37 return res;

38 }

39 };

40

41 // Two pointer, constant space, solution

42 class Solution {

43 public:

44 string removeStars(string s) {

45 int i = 0;

46 for (int j = 0; j < s.size(); j++) {

47 if (s[j] == '*')

48 i--;

49 else

50 s[i++] = s[j];

51 }

52 return s.substr(0, i);

53 }

54 };