java – 最高的“有价值”回文

发布时间：2020-12-15 02:58:37 所属栏目：Java 来源：网络整理

导读：所以几个月前我正在接受编程采访,这个问题因为某些原因而惹恼了我.我能想到几种解决方案,但大多数解决方案效率极低.虽然我已经有多年的编程能力,但我目前正在大学攻读CS学位,所以我的参考点可能不完整.我希望有人可以提供一些可能的解决方案： “给定一组字

所以几个月前我正在接受编程采访,这个问题因为某些原因而惹恼了我.我能想到几种解决方案,但大多数解决方案效率极低.虽然我已经有多年的编程能力,但我目前正在大学攻读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)

确保在使用时标记用于开头的字符串和结束时使用的字符串.
并且一定要考虑递归对“使用”标记的影响.

然后挑选得分最高的回文.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!