Problem Statement:


Given a string determine if the string is a palindrome.

Solution:



This problem can be solved by Dynamic Programming approach. Let's take an example: for a string "abba" if we know if the string "bb" is palindrome or not, based on that we can determine if the whole string is palindrome. If "bb" is palindrome then all we need to check if the first 'a' matched the last 'a', if they match then the string is palindrome.

If "bb" is not palindrome then "abba" cannot be palindrome.

So this problem exhibits Optimal Sub-structures property. If we know results for shorter length string, using that we can compute result for higher length string and eventually for the whole string.

Please take a look at the template we have discussed in Dynamic Programming with 1 String chapter. The code below shows how using the template we can solve this problem seamlessly.

Java Code:



Login to Access Content




Python Code:



Login to Access Content




Instructor:



If you have any feedback, please use this form: https://thealgorists.com/Feedback.



Help Your Friends save 40% on our products

wave