Given string s, find minimum number of operations to convert it into Palindromic string. Operations are: 1) Insert a new character anywhere into the string (including its beginning and end). 2) Remove a single character. 3) Replace a single character by another character.
You can use dynamic programming approach to solve this problem. dp[i, j] — minimum number of operations to convert substring s[i..j] into palindrome. Below is the transitions:
Obviously, dp[i, j] = 0 if i >= j
And in general dp[i, j] is minimum of:
The answer will be stored in dp[0, len(s)-1]
Hope that helps!
Is there any faster solution?
Thanks!!
you can read more from here it's classic dp problem just find edit distance between the string and it's reverse