java - 最高 "Valued"回文

Question

所以几个月前我在参加编程面试时，由于某种原因这个问题让我绊倒了。我可以想到几个解决方案，但其中大多数似乎效率极低。虽然多年来我一直以某种身份进行编程，但我目前正在大学攻读 CS 学位，所以我的引用点可能不完整。我希望这里有人可以提供一些可能的解决方案:

“给定一组字符串和相关的数字‘值’，从这些字符串中组装一个回文，其值(由用于创建它的字符串的总和定义)是可能的最高值。”

可以提供的字符串数量没有限制，有些字符串可能不会被使用。

例子:“ASD”- 3“dsa”- 5“应用程序”- 1

结果将是值为 9 的“asdappadsa”。

我的想法是尝试所有顺序的所有字符串，然后放弃一个，从最低值的开始，但该解决方案是 O(N!)，我认为这不行。

(首选语言是 C 和 Java，但不管用什么)

编辑:澄清。提供的每个字符串只能使用一次，并且必须完全按照提供的方式使用，但您可以选择不使用回文中的任何字符串。您不能使用提供的字符串的子字符串，也不能反转字符串。

Answer 1

用“所有回文”替换“所有字符串”，问题空间变得更小。

将字符串分成 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)   

使用时一定要标明开头和结尾的字符串。并且一定要考虑递归对“已用”标记的影响。

然后选择得分最高的回文。