Confused101's blog

Convert to palindrome.
By Confused101, history, 8 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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:

  • dp[i+1, j-1] if s[i] == s[j]
  • dp[i+1][j-1] + 1 # replace character s[i] to s[j] OR s[j] to s[i]
  • dp[i+1, j] + 1 # remove i-th character OR insert a new character right after j-th position
  • dp[i, j-1] + 1 # remove j-th character OR insert a new character right before i-th position

The answer will be stored in dp[0, len(s)-1]

Hope that helps!

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

you can read more from here it's classic dp problem just find edit distance between the string and it's reverse

→ Reply