Determine if a given string is palindrome or not

Write a program to determine if a given string is palindrome or not. A palindromic string is a string that remains the same when its characters are reversed. Like “ABCBA”, for example, it is “symmetrical”.

 
 

A simple solution would be to reverse the string and compare if the original string is equal to the reversed string or not. If they are found to be equal, we can say that the given string is a palindrome. This solution, though simple and concise, is not in-place. Also, the comparison function might end up iterating all the way till end of the string. This is linear on paper but we still can do better.
 

We can easily check for palindromic string in-place without using extra string and without iterating through the complete string. The idea is to take two pointers that points to the beginning and ending of the string and start comparing characters pointed by them. First iteration will check if the first and last characters are the same and the next iteration will compare next pair and so on.. If a mismatch happens at any point, then we can say that the given string is not palindrome.

 

Iterative version –

C++

Download   Run Code

Java

Download   Run Code


 

Recursive version –

 

Download   Run Code

 

Single line recursive version –

 

We can also re-write above recursive code in single line (remember, an interviewer can ask this as a follow-up question or even start with this problem itself) –

 

Download   Run Code

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz