所以几个月前我正在接受编程采访,这个问题因为某些原因而惹恼了我.我能想到几种解决方案,但大多数解决方案效率极低.虽然我已经有多年的编程能力,但我目前正在大学攻读CS学位,所以我的参考点可能不完整.我希望有人可以提供一些可能的解决方案：
“给定一组字符串和相关的数字’值,’从这些字符串组装回文,其值(由用于创建它的字符串之和定义)是最高的.”
可以提供多少个字符串没有限制,可能不使用某些字符串.
例：
“asd” – 3
“dsa” – 5
“appa” – 1
结果将是“asdappadsa”,值为9.
我的想法是尝试所有顺序中的所有字符串,然后从最低值的一个开始删除一个,但该解决方案是O(N！)并且我认为不行.
(首选语言是C和Java,但不管是什么工作)
编辑：澄清.提供的每个字符串只能使用一次,并且必须完全按照提供的方式使用,但您可以选择不使用回文中的任何字符串.您不能使用提供的字符串的子字符串,也不能反转字符串.
解决方法
用“所有回文”替换“所有字符串”,问题空间变得更小.
将字符串分成26个子集.
Strings beginning with x (for 'a' <= x <= 'z') [or whatever the set of "letters" is]
现在将它们分成另外26个子集
Strings ending with y ( for 'a' <= y <= 'z')
请注意,每个字符串都显示在“开头”设置和“结束”设置中.
使用这些集来指导创建所有可能的回文.
Start with two empty strings: prefix and suffix
for each string in the original set
assign it to the prefix
call recursiveFunction(prefix,suffix)
def recursiveFunction(prefix,suffix):
if prefix + <anything> + suffix cannot form a palindrome return
if prefix + suffix is a palindrome,remember it
while you have unused strings
if the suffix is shorter than the prefix
Look at the first unmatched character in the prefix
for each unused string that ends in that character
call recursiveFunction(prefix,string + suffix)
else if prefix is shorter than suffix
look at the last unmatched character in the suffix
for each unused string that ends with that character
call recursiveFunction(prefix + string,suffix)
else // suffix and prefix have equal lenghths
for each unused string
call recursiveFunction(prefix + string,suffix)
确保在使用时标记用于开头的字符串和结束时使用的字符串.
并且一定要考虑递归对“使用”标记的影响.
然后挑选得分最高的回文.
