Command Palette

Search for a command to run...

Hectal
Problem 12.3 · RecursionEasy

Reverse a String Recursively

PatternRecursionTwo Pointers: Opposite Ends

What it teaches: A loop rewritten as recursion: swap the ends, then recurse on the inside. Shows how depth becomes stack space.

Practise it on judges as “Reverse String”.

The problem

Reverse a char[] s in place, using recursion.

Example 1

Input: s = [h, e, l, l, o]
Output: [o, l, l, e, h]

Constraints

  • 1 ≤ s.length ≤ 10⁵

Pattern clues in the wording

  • → The inside of the array is the same problem, smaller

These clues point to Recursion: Solve the problem by solving a smaller version of it, with a base case that stops the calls.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public void reverseString(char[] s) {
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s = ["h","e","l","l","o"]
["o","l","l","e","h"]
2
s = ["H","a","n","n","a","h"]
["h","a","n","n","a","H"]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Recursive two pointers · O(n)
1

Recursive two pointers

Time O(n) Space O(n) stack

helper(l, r): if l >= r stop; swap s[l], s[r]; recurse on (l + 1, r − 1). Depth is n / 2.

Approach 1
class Solution {
    public void reverseString(char[] s) {
        helper(s, 0, s.length - 1);
    }

    private void helper(char[] s, int l, int r) {
        if (l >= r) return;
        char t = s[l]; s[l] = s[r]; s[r] = t;
        helper(s, l + 1, r - 1);
    }
}

Verdict: Fine for moderate n; the iterative version from Module 0 uses O(1) space.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One character
  • Even and odd lengths

Mistakes people make

  • Recursing first and swapping after (still works here, but changes the order of work).

Interview

Follow-up questions

Is recursion a good choice for n = 10⁵ here?