I*******g
发帖数: 7600 | 1 Given a string, every step you can add/delete/change one character at any
position. Minimize the step number to make it a palindrome.
. |
x********g
发帖数: 43 | |
w***u
发帖数: 156 | |
l*y
发帖数: 70 | 4 Reverse string, make n by n table, I,j means minimum steps to match s(0...i)
to t(0...j) |
w***u
发帖数: 156 | |
R****i
发帖数: 104 | 6 如果 k steps 可以把一个长度为 n String变换成palindrome。 如果现在多加一个字
符使原来的String 变成 n+1 长度，那新的步骤可以分为三种：
1：the (n+1)th 字符直接和前面的配成 palindrome， 如果可能，k steps
2：change 第（n+1) 字符 和前面的组成 palindrome，k+1 steps
3: 第一个字符和第（n+1)个字符匹配好，看看中间的（n-1)个自己最少的step数，
三者取最小的。
大概思路是这样，望大牛们指正一下。
【在 I*******g 的大作中提到】
: Given a string, every step you can add/delete/change one character at any
: position. Minimize the step number to make it a palindrome.
: .
|
S********t
发帖数: 3431 | 7 不work吧，你这新来的字符跟谁配啊
楼上的大牛们已经给你指了思路啊，要练练 follow hint
【在 R****i 的大作中提到】
: 如果 k steps 可以把一个长度为 n String变换成palindrome。 如果现在多加一个字
: 符使原来的String 变成 n+1 长度，那新的步骤可以分为三种：
: 1：the (n+1)th 字符直接和前面的配成 palindrome， 如果可能，k steps
: 2：change 第（n+1) 字符 和前面的组成 palindrome，k+1 steps
: 3: 第一个字符和第（n+1)个字符匹配好，看看中间的（n-1)个自己最少的step数，
: 三者取最小的。
: 大概思路是这样，望大牛们指正一下。
|
f*******s
发帖数: 182 | |
r*******g
发帖数: 1335 | 9 有点不确定，为何reverse之后再edit distance就是要求的答案呢 |
M**a
发帖数: 25 | |
