Check whether the given string is a palindrome

Posted by on Mar 31, 2024

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).

Related


Print all permutations of a given string

Find all substrings of a string in "O (n^2)" time

Power Set: Print all non-empty subsequences of a string

Reverse words in a given string

Longest Common Prefix in an Array of Strings

Print all subsequences of a string

Check if two given strings are isomorphic to each other

Swap all occurrences of two characters to get lexicographically smallest string

Check if two strings are equal or not after processing backspace

Transform One String to Another with a Minimum Number of Operations