Блог пользователя Confused101

Автор Confused101, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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!

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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