Check If a String Reads the Same Forwards and Backwards — Recursively
Solve this Problems, determine whether it reads the same forwards and backwards.
The two-pointer idea — compare the outer characters, then move inward — translates directly into recursion: each call handles exactly one pair, and if that pair matches, the rest of the question ("does everything strictly between them also form a palindrome?") is answered by recursing on the smaller window one step in from each side. The base case, where the two pointers meet or cross, means every pair along the way matched successfully, so the answer is true. The recursive version does the exact same comparisons as the iterative one — it just spends a stack frame per pair instead of a single loop variable.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 15 - ◆
s consists of lowercase English letters only
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Iterative — Two Pointers, Single Pass
OptimalWalk two pointers inward from both ends at once, comparing characters as they go. The moment any pair disagrees, the string isn't a palindrome — stop and return false immediately. If the pointers meet or cross without ever disagreeing, every pair matched, so it is one. No extra memory grows with the input.
O(n)O(1)1class Solution {
2 public boolean isPalindromeRecursive(String s) {
3 int left = 0, right = s.length() - 1;
4 while (left < right) {
5 if (s.charAt(left) != s.charAt(right)) return false;
6 left++;
7 right--;
8 }
9 return true;
10 }
11}Recursive — Shrink the Window by One Pair Each Call
GoodExpress the same two-pointer idea recursively: if the two ends of the current window don't match, it's not a palindrome — immediately false. If they do match, the answer for the whole window is exactly the answer for the smaller window one step in from each side — so recurse on that. The base case (the pointers meeting or crossing) means every pair along the way matched. Same comparisons as the loop, just expressed as a chain of calls instead of repeated iterations.
O(n)O(n) call-stack space1class Solution {
2 public boolean isPalindromeRecursive(String s) {
3 return check(s, 0, s.length() - 1);
4 }
5
6 private boolean check(String s, int left, int right) {
7 if (left >= right) return true;
8 if (s.charAt(left) != s.charAt(right)) return false;
9 return check(s, left + 1, right - 1);
10 }
11}