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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果 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 | |