s***d
发帖数: 2 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: saiad (happy), 信区: JobHunting
标 题: 一道C++面试题
发信站: BBS 未名空间站 (Thu Jan 4 19:52:27 2007), 转信
A palindrome is a String that is spelled the same forward and backwards.
Given a String base that may or may not be a palindrome, we can always force
base to be a palindrome by adding letters to it. For example, given the
word "RACE", we could add the letters "CAR" to its back to get "RACECAR" (
quotes for clarity only). But, we are not restricted to adding letters at
the ba | O*******d
发帖数: 20343 | | q*****g
发帖数: 72 | 3 可能是用c＋＋写出code吧
【在 O*******d 的大作中提到】
: 这个和C++有什么关系？
| r********g
发帖数: 1351 | | c*****z
发帖数: 182 | 5 hi, can you give some more detail on how to use dp
are you going to a fixe a point as pivot and match th strings on both sides
using edit distance?
【在 r********g 的大作中提到】
: DP
| f********r
发帖数: 50 | 6 post some analysis from topcoder
A key observation is that, to make the shortest possible palindrome out of
base, you should never add letters to both the front and back of the string.
If you were to do so, then you could make an even shorter palindrome by
removing the first and last characters that you added. Therefore, the
shortest palindrome that you can make out of base must either start with the
first letter of base or end with the last letter of base (or both, if the
first and last letters
【在 c*****z 的大作中提到】
: hi, can you give some more detail on how to use dp
: are you going to a fixe a point as pivot and match th strings on both sides
: using edit distance?
| f****i
发帖数: 98 | 7 Job Hunting版给出的breadth-first-search的方法更好。
top-coder的递归解法本质上是depth-first-search，遍历搜索空间所有的节点，
再比较叶子节点的高度，取最小值。而breadth-first-search可以直接找到高度
最小的叶子节点，而避免遍历整个搜索空间。
另外，topcoder解答中的memoization，在breadth-first-search里面也可以很容易
的实现。
of
string.
the
【在 f********r 的大作中提到】
: post some analysis from topcoder
: A key observation is that, to make the shortest possible palindrome out of
: base, you should never add letters to both the front and back of the string.
: If you were to do so, then you could make an even shorter palindrome by
: removing the first and last characters that you added. Therefore, the
: shortest palindrome that you can make out of base must either start with the
: first letter of base or end with the last letter of base (or both, if the
: first and last letters
|
|
