S******0
发帖数: 71 | 1 make any given string a palindrome by adding the minimum number of character
这道题是用DP解的吗？ |
c*****t
发帖数: 93 | |
b*****u
发帖数: 648 | 3 这个不就是leetcode上的longest palindrome吗， 添最少等价于删最少 |
d**********x
发帖数: 4083 | 4 肿么等价？愿闻其详
【在 b*****u 的大作中提到】
: 这个不就是leetcode上的longest palindrome吗， 添最少等价于删最少
|
l*******b
发帖数: 2586 | 5 是longest pal sub sequence吧? 比substring简单点.找到这个然后添加元素是不是就
可以啦?
貌似也可以这样想: 从一头开始看, 如果和另一头不一样, 那么两头必须有一头添加一
个, 添加以后同时删掉, 等价于减少了一个字符, 就可以用dp啦 |
f*****e
发帖数: 2992 | 6 可以找S和S逆的最大公共字符串。
【在 l*******b 的大作中提到】
: 是longest pal sub sequence吧? 比substring简单点.找到这个然后添加元素是不是就
: 可以啦?
: 貌似也可以这样想: 从一头开始看, 如果和另一头不一样, 那么两头必须有一头添加一
: 个, 添加以后同时删掉, 等价于减少了一个字符, 就可以用dp啦
|
d**********x
发帖数: 4083 | 7 我咋觉得是S和S逆的最大公共子序列呢
是就
加一
【在 f*****e 的大作中提到】
: 可以找S和S逆的最大公共字符串。
|
f*****e
发帖数: 2992 | 8 Yes, that's what I mean.
【在 d**********x 的大作中提到】
: 我咋觉得是S和S逆的最大公共子序列呢
:
: 是就
: 加一
|
b*****u
发帖数: 648 | 9 不对，我想简单了，没有考虑到回文两头都多出不同字符的反例, 比如 cabad这样
never mind
【在 d**********x 的大作中提到】
: 肿么等价？愿闻其详
|
c********t
发帖数: 5706 | 10 顶，最近对原有字符串变形问题挺多。
【在 d**********x 的大作中提到】
: 我咋觉得是S和S逆的最大公共子序列呢
:
: 是就
: 加一
|
|
|
p****e
发帖数: 3548 | 11 找出对称点，越靠近中间越短
character
【在 S******0 的大作中提到】
: make any given string a palindrome by adding the minimum number of character
: 这道题是用DP解的吗？
|
S******0
发帖数: 71 | 12
然后呢？
【在 d**********x 的大作中提到】
: 我咋觉得是S和S逆的最大公共子序列呢
:
: 是就
: 加一
|
c********t
发帖数: 5706 | 13 然后brute force? 不知大牛们还有更好的解法吗？
【在 S******0 的大作中提到】
:
: 然后呢？
|
d**********x
发帖数: 4083 | 14 是啊。。求出最大公共子序列之后，这就是原字符串中的最大对称子序列
然后标记所有子序列元素位置
从两头往中间走，如果两个元素不都是子序列里面的元素，就加一个或两个元素去
match，直到两个都是为止，然后继续往中间走。。多straight forward。。。
然后假设我们可以添加更少的字符找到一个解，那么去掉这些字符以及对应的对称元素
后我们必然还是得到一个对称的字串，且比最大对称字串长，矛盾
【在 c********t 的大作中提到】
: 然后brute force? 不知大牛们还有更好的解法吗？
|
j*****y
发帖数: 1071 | 15 感觉还是dp 吧
dp[i][j] 表示把 s[i,...j]变成 palindrome的最少添加的单词数目
dp[i][j]=
dp[i + 1][j - 1], if(s[i] == s[j])
1 + min(dp[i+ 1][j], dp[i][j - 1]), if(s[i] != s[j])
【在 d**********x 的大作中提到】
: 是啊。。求出最大公共子序列之后，这就是原字符串中的最大对称子序列
: 然后标记所有子序列元素位置
: 从两头往中间走，如果两个元素不都是子序列里面的元素，就加一个或两个元素去
: match，直到两个都是为止，然后继续往中间走。。多straight forward。。。
: 然后假设我们可以添加更少的字符找到一个解，那么去掉这些字符以及对应的对称元素
: 后我们必然还是得到一个对称的字串，且比最大对称字串长，矛盾
|
p*****2
发帖数: 21240 | 16
嗯。dp想法比较直接。
【在 j*****y 的大作中提到】
: 感觉还是dp 吧
: dp[i][j] 表示把 s[i,...j]变成 palindrome的最少添加的单词数目
: dp[i][j]=
: dp[i + 1][j - 1], if(s[i] == s[j])
: 1 + min(dp[i+ 1][j], dp[i][j - 1]), if(s[i] != s[j])
|
d**********x
发帖数: 4083 | 17 一回事。。
这个dp的状态也是O(n^2)
不过说起来我一开始想的也是dp。。。
元素
【在 j*****y 的大作中提到】
: 感觉还是dp 吧
: dp[i][j] 表示把 s[i,...j]变成 palindrome的最少添加的单词数目
: dp[i][j]=
: dp[i + 1][j - 1], if(s[i] == s[j])
: 1 + min(dp[i+ 1][j], dp[i][j - 1]), if(s[i] != s[j])
|
r*********n
发帖数: 4553 | 18 ....我觉得是substring呢....
原题需要添加的字符等于 S - the longest palindromic substring ending at S[end
-1]
To find the longest palindromic substring ending at S[end-1]:
reverse S, using suffix tree to find the longest common substring (ending at
S[end-1]) of S and S_r at O(n) time
overall time complexity is O(n)
edit:
我以为只能在后面加，原来是不限位置。
【在 d**********x 的大作中提到】
: 我咋觉得是S和S逆的最大公共子序列呢
:
: 是就
: 加一
|
p****e
发帖数: 3548 | 19 s[0]也行的
end
at
【在 r*********n 的大作中提到】
: ....我觉得是substring呢....
: 原题需要添加的字符等于 S - the longest palindromic substring ending at S[end
: -1]
: To find the longest palindromic substring ending at S[end-1]:
: reverse S, using suffix tree to find the longest common substring (ending at
: S[end-1]) of S and S_r at O(n) time
: overall time complexity is O(n)
: edit:
: 我以为只能在后面加，原来是不限位置。
|
o****d
发帖数: 2835 | 20
end
这个不太对？考虑cbba 不能限制在ending在两端的
【在 r*********n 的大作中提到】
: ....我觉得是substring呢....
: 原题需要添加的字符等于 S - the longest palindromic substring ending at S[end
: -1]
: To find the longest palindromic substring ending at S[end-1]:
: reverse S, using suffix tree to find the longest common substring (ending at
: S[end-1]) of S and S_r at O(n) time
: overall time complexity is O(n)
: edit:
: 我以为只能在后面加，原来是不限位置。
|
|
|
r*********n
发帖数: 4553 | 21
结果是什么
cbbabbc
the longest palindromic substring ending at S[end-1] is S[end-1] itself,
which is a
hence we should pad bbc (from cbb before a) after a
又看了下原题，我理解错题了，我以为只能在后面加
【在 o****d 的大作中提到】
:
: end
: 这个不太对？考虑cbba 不能限制在ending在两端的
|
c******3
发帖数: 60 | 22 这个是正解
【在 j*****y 的大作中提到】
: 感觉还是dp 吧
: dp[i][j] 表示把 s[i,...j]变成 palindrome的最少添加的单词数目
: dp[i][j]=
: dp[i + 1][j - 1], if(s[i] == s[j])
: 1 + min(dp[i+ 1][j], dp[i][j - 1]), if(s[i] != s[j])
|
f****s
发帖数: 74 | 23 这个adding是只能在两头adding还是可以在任意位置adding？
character
【在 S******0 的大作中提到】
: make any given string a palindrome by adding the minimum number of character
: 这道题是用DP解的吗？
|
o****d
发帖数: 2835 | 24 是不是就是跟longest palindrome subsequence 等价的
【在 j*****y 的大作中提到】
: 感觉还是dp 吧
: dp[i][j] 表示把 s[i,...j]变成 palindrome的最少添加的单词数目
: dp[i][j]=
: dp[i + 1][j - 1], if(s[i] == s[j])
: 1 + min(dp[i+ 1][j], dp[i][j - 1]), if(s[i] != s[j])
|
f*****e
发帖数: 2992 | 25 of course not.
【在 o****d 的大作中提到】
: 是不是就是跟longest palindrome subsequence 等价的
|
x*********w
发帖数: 533 | 26 const char* minimumPadding(const char* szStr, char res[])
{
if (NULL == szStr || *szStr == 0 || NULL == res)
return 0;
int nLen = strlen(szStr);
int rec[100][100] = { 0 };
for (int i = 0; i < nLen-1; i++)
{
rec[i][i+1] = szStr[i] == szStr[i+1] ? 0 : 1;
}
for (int i = 2; i < nLen; i++)
{
for (int j = 0; j < nLen-i; j++)
{
rec[j][j+i] = 1 + min(rec[j+1][j+i], rec[j][j+i-1]);
if (szStr[j] == szStr[j+i])
rec[j][j+i] = min(rec[j+1][j+i-1], rec[j][j+i]);
}
}
int nResLen = rec[0][nLen-1] + nLen;
res[nResLen] = 0;
char* p = res;
char* q = res + nResLen - 1;
int i = 0;
int j = nLen-1;
while (p <= q)
{
char c = 0;
if (szStr[i] == szStr[j])
{
c = szStr[i];
i++, j--;
}
else
{
if (rec[i][j-1] < rec[i+1][j])
{
c = szStr[j];
j--;
}
else
{
c = szStr[i];
i++;
}
}
*p++ = c;
*q-- = c;
}
return res;
}
做的还是太慢了... |
p*****2
发帖数: 21240 | 27
怎么还不转Java？转了之后拿offer的机率要大很多
【在 x*********w 的大作中提到】
: const char* minimumPadding(const char* szStr, char res[])
: {
: if (NULL == szStr || *szStr == 0 || NULL == res)
: return 0;
: int nLen = strlen(szStr);
: int rec[100][100] = { 0 };
: for (int i = 0; i < nLen-1; i++)
: {
: rec[i][i+1] = szStr[i] == szStr[i+1] ? 0 : 1;
: }
|
