Reverse String

from dataclasses import dataclass, field

Problem

Write a function reverse_string_using_stack(string) that uses a stack to reverse the characters in a string.

Constraints and Assumptions

Placeholder for now.

Implementation

@dataclass(frozen=False, init=True)
class Solution:
    stack: StackList[str] = field(default_factory=StackList)

    def reverse_string_using_stack(self, string: str) -> None:
        """Reverse a string using stack."""
        reversed_string = ""

        for char in string:
            self.stack.push(char)

        while not self.stack.is_empty():
            reversed_string += self.stack.pop()

        return reversed_string

string = "abcdefg"
expected = "gfedcba"

Solution().reverse_string_using_stack(string) == expected

True

Time Complexity

Assume the string has length \(n\).

From Stack List Time Complexity, operations such as push, pop, is_empty() and += here are all \(\O(1)\).

And since we traverse the given string one character at a time for at most \(n\) times, then the time complexity is

\[ \O(1) \times n \approx \O(n) \]

Space Complexity

Assume the string has length \(n\).

The space complexity is at most \(\O(n)\) as we are just maintaining a stack with at most \(n\) elements pushed in.