Check If Given String Is A Palindrome Using Recursion Problem Statement
Check if the given string is a palindrome or not, using recursion.\
Ignore punctuation marks, spaces and case of letters.\
Consider any character as a punctuation character if it belongs to {'.', ',', '!', '-', ';', ':', ''', '"'}.
Example One
{
"s": "racecar"
}
Output:
1
Example Two
{
"s": "Never a foot too far, even."
}
Output:
0
Notes
Constraints:
- 1 <= length of the given string <= 100000
- The input string contains letters only from uppercase letters ('A' - 'Z'), lowercase letters ('a' - 'z'), spaces or above mentioned punctuation marks.
- Only the checking of palindrome part needs to be done recursively. Other things e.g. finding length of the input etc. can be done iteratively.
- Assume that you are not allowed to modify the input string.
- Solution with linear time complexity is expected.
We have provided one solution.
Throughout the editorial, we will refer to the input string as s and the length of s by n.
Check If Given String Is A Palindrome Using Recursion Solution: Optimal
Time Complexity
O(n).
Because in worst case we need to traverse the whole string.
(Worst case for time complexity will be when input string contains only punctuation marks.)
Auxiliary Space Used
By looking at the code, at first glance it might look like it uses O(1) extra space but it is not O(1).
It is,
O(n).
Because recursive function uses the function call stack! (Local variables and some other details will be stored before making another function call.)
Worst case for auxiliary space used will also be when input string contains only punctuation marks.
Suppose s = ".........." that is 10 dots, then our check for palindrome will go like,
recursive_palindrome_check(s, 0, 9) ->
recursive_palindrome_check(s, 1, 9) ->
recursive_palindrome_check(s, 2, 9) ->
recursive_palindrome_check(s, 3, 9) ->
recursive_palindrome_check(s, 4, 9) ->
recursive_palindrome_check(s, 5, 9) ->
recursive_palindrome_check(s, 6, 9) ->
recursive_palindrome_check(s, 7, 9) ->
recursive_palindrome_check(s, 8, 9) ->
recursive_palindrome_check(s, 9, 9)
So we will be making total 10 calls (that is n) to the same function.
When we will reach last function call that is recursive_palindrome_check(s, 9, 9), we will have information of all previous functions stored on function call stack.
Space Complexity
O(n).
Space used for input: O(n).
Auxiliary space used: O(1).
Space used for output: O(n).
So, total space complexity: O(n).
Code For Check If Given String Is A Palindrome Using Recursion Solution: Optimal
/*
Asymptotic complexity in terms of the length of input string \`s\` ( = \`n\`) :
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/
/*
Function to recursively check, if string s in range start to end (both inclusive), is a valid
palindrome or not.
*/
bool recursive_palindrome_check(string &s, int start, int end)
{
if (start >= end)
{
return true;
}
if (isalpha(s[start]) == false)
{
return recursive_palindrome_check(s, start + 1, end);
}
if (isalpha(s[end]) == false)
{
return recursive_palindrome_check(s, start, end - 1);
}
if (tolower(s[start]) == tolower(s[end]))
{
return recursive_palindrome_check(s, start + 1, end - 1);
}
return false;
}
bool is_palindrome(string &s) {
return recursive_palindrome_check(s, 0, s.length() - 1);
}
We hope that these solutions to palindrome validation have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.
We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE webinar.
.png)
