Two problems, one recursion, one changed line.
Walk two pointers inward and stop when they meet. The only difference is whether each frame compares the two ends or swaps them.
Press Next to make the first call.
Both versions stop at r <= l, and that single condition covers everything.
| situation | how it stops | try |
|---|---|---|
| odd length | the pointers meet, l == r | racecar |
| even length | the pointers cross, r < l | abba |
| empty | already crossed before the first step | (empty) |
The pointers only reach a crossed state by matching at every step on the way in, so true is the only correct answer there. My first attempt returned false, which passed every odd-length palindrome and failed every even-length one. Run abba and watch where it lands.
Flip between the two jobs on the same word. The pointers move identically; only the work at each level changes.
Once the traversal is right, a new problem is often just a different line in the middle.
Note where the work sits: both act before recursing, so the outermost pair is handled first. That makes these pre-order, like LC 21 and unlike LC 206. See where the work happens.
Both are O(n) time and O(n) space, because about n/2 frames are open at the deepest point. That stack on the right is the space. An iterative two-pointer loop does the same work in O(1), and LC 344 asks for O(1) extra memory, so the recursive version is accepted but not strictly what the problem wants.
Pass the string by const& with two indices, never by value. Copying it at every level turns O(n) into O(n²).