Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem 2: Reverse a String (easy)

Problem Statement

Given a string, write a function that uses a stack to reverse the string. The function should return the reversed string.

Examples

Example 1:

Input: "Hello, World!"
Output: "!dlroW ,olleH"

Example 2:

Input: "OpenAI"
Output: "IAnepO"

Example 3:

Input: "Stacks are fun!"
Output: "!nuf era skcatS"

Constraints:

  • 1 <= s.length <= 10<sup>5</sup>
  • s[i] is a printable ascii character.

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
M

mansidixit989

· 3 years ago

The reason is strings are immutable Every time we append a char to a string it is going to create a new copy of string costing O(n) in each iteration

Show 4 replies
M

manishashokgiri2.0

· 4 months ago

Rather than doing this

// Use a list to collect reversed characters
        List<Character> reversedList = new ArrayList<>(s.length());

        // Pop characters from the stack and add them to the list
        while (!stack.isEmpty()) {
            reversedList.add(stack.pop());
        }

We can make it avoid this loop.

Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for(char c : chars) {
            stack.push(c);
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
T

traviswlilleberg

· 9 months ago

/*
In JavaScript (and possibly other languages), the reversedList array is pointless and creates unnecessary space overhead for the function. You can build a string directly from the stack, like so:
*/

class Solution {
    reverseString(s) {
        if(!s.length) { return s }

        const stack = s.split('');
        let output = '';

        while(stack.length) {
            output += stack.pop();
        }

        return output;
    }
}
A

axle982

· 2 years ago

why doesn't a for in loop work instead of using a while loop

Show 2 replies
J

johannes.welsch

· 2 years ago

The solutions says that the variable reversedString has a space complexity of O(1). But if we have a string of a million characters, it will create an additional string of a million characters, which means it's O(N)?

Show 1 reply