b******7
发帖数: 79 | 1 Find minimum number of characters that need to be inserted into a string (
anywhere in the string) to make it a palindrome..(Hint: Interviewer expected
a Dynamic Programming kind of solution)
line在http://www.careercup.com/question?id=260670
给出的解中貌似没有合适的。怎么用dynamic programming解啊？好象不能简单的说第
一个和最后一个不match，就插入。。。请高手指教！ |
k*k
发帖数: 49 | 2 just some thoughts... i may be wrong... |
m*****f
发帖数: 1243 | 3 抛砖引玉, 写下基本思路
assume string a0a1a2....an
dp[i][j] = the number of chars to insert to make string from ai to aj to be
palindrome.
We know dp[i][i] = 0 (a single char string is always palindrome).
recursive run:
if (ai == aj) {
dp[i][j] = dp[i+1][j-1]
} else {
dp[i][j] = min(dp[i][j-1]+1, dp[i+1][j]+1)
} |
g*******y
发帖数: 1930 | |
k***e
发帖数: 556 | 5 提一点问题
考虑a[i:j]
ai==aj时,在最优解中定是i，j配对吗？或者说，一定存在一个最优解使得i，j配对吗？
好像如此，但是很难证明 |
S**Y
发帖数: 136 | 6 替你实现一下.
要注意的是填坑的顺序.
int palindrome(string a)
{
int len = a.length();
int** V = new int*[len+1];
for(int i = 0; i <= len; i++)
{
V[i] = new int[len + 1];
}
for(int i = 0; i <= len; i++)
{
V[0][i] = 0;
}
for(int i = 0; i <= len; i++)
{
V[i][0] = 0;
}
for(int k = 0; k < len; k++)
{
int i, j;
for(i = 1, j = i + k; i <= len,j <= len; i++, j++)
{
if(k == 0)
V[i][j] = 0;
|
b***e
发帖数: 1419 | 7 Easy. Computer LCS of s and reverse of s.
Google Longest Common Sequence, it is standard.
(
expected
【在 b******7 的大作中提到】
: Find minimum number of characters that need to be inserted into a string (
: anywhere in the string) to make it a palindrome..(Hint: Interviewer expected
: a Dynamic Programming kind of solution)
: line在http://www.careercup.com/question?id=260670
: 给出的解中貌似没有合适的。怎么用dynamic programming解啊？好象不能简单的说第
: 一个和最后一个不match，就插入。。。请高手指教！
|
m*****f
发帖数: 1243 | 8 能解释下么, 我不太懂
【在 b***e 的大作中提到】
: Easy. Computer LCS of s and reverse of s.
: Google Longest Common Sequence, it is standard.
:
: (
: expected
|
a****n
发帖数: 1887 | 9 reverse string
DP calc LCS |
H****r
发帖数: 2801 | 10 This almost the same as LCS
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i := 0..m
C[i,0] = 0
for j := 0..n
C[0,j] = 0
for i := 1..m
for j := 1..n
if X[i] = Y[j]
C[i,j] := C[i-1,j-1] + 1
else:
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]
Guess hoof is right.
be
【在 m*****f 的大作中提到】
: 抛砖引玉, 写下基本思路
: assume string a0a1a2....an
: dp[i][j] = the number of chars to insert to make string from ai to aj to be
: palindrome.
: We know dp[i][i] = 0 (a single char string is always palindrome).
: recursive run:
: if (ai == aj) {
: dp[i][j] = dp[i+1][j-1]
: } else {
: dp[i][j] = min(dp[i][j-1]+1, dp[i+1][j]+1)
|
|
|
H*****L
发帖数: 5705 | 11 return (strlen - LCS)?
【在 a****n 的大作中提到】
: reverse string
: DP calc LCS
|
a****n
发帖数: 1887 | 12 YES, my solution
http://www.cnblogs.com/asuran/archive/2009/10/14/1583117.html
【在 H*****L 的大作中提到】
: return (strlen - LCS)?
|
b******7
发帖数: 79 | 13 上面写solution是LCS of s 和 reverse(s)的朋友似乎需要更多解释一下？因为明显
xyyyz和他的reverse zyyyx的lcs is yyy,那么yyy和这道题的solution是什么关系？ |
b******7
发帖数: 79 | 14 BTW, xyyyz的solution应该是xzyyyzx. |
b******7
发帖数: 79 | |
m*****f
发帖数: 1243 | 16 我列的dp式子明明是对的
【在 b******7 的大作中提到】
: 总结一下，上面的方法都错了。希望大牛能指教！
|
b******7
发帖数: 79 | 17 sorry, 上面的求LCS of s 和 reverse(s)是对的。我自己没理解。当然他们并没有解
释清楚。我解释一下，因为palindrome是 X X_r (用X_r to represent the reversed
x). If we want to transform X to a palindrome with minimum amount of
insertion(note we cannot use replacement and deletion and thus this is
different from edit distance), we have to take advantage of the palindrome
within X as much as possible. That is, for xyyyz, yyy itself is a Palindrome
, therefore, we do not want to disturbe it (as much as we can) when we
transform X. Therefore, |
