A string s is given, the task is to check if s is a Palindrome or not using recursion.
A string is said to be palindrome if reverse of the string is same as string itself.
Example 1: Check if "apple" is a palindrome.
Input: "apple"
Output: false
Example 2: Check if "appa" is a palindrome.
Input: "appa"
Output: true
Example 3: Check if "abcdedcba" is a palindrome.
Input: "abcdedcba"
Output: false
Solutions
Method 1: Recursion
Here we will compare first and last characters and recur for remaining substring. If string has only one character it is an palindrome, this will make the base condition.
Complexity
In every fn call, we are increasing start index and decreasing end index, that means fn is called n/2 or n/2+1 times for a string of size n; so Time Complexity is O(n).
We are also storing startIndex and endIndex in every call, so Space Complexity is 2n or O(n).