string - CodeJam 2014 : Solution for The Repeater

Question

我参加了code jam，我成功解决了The Repeater Challenge的小输入但似乎无法找出多个字符串的方法。

谁能给出用于多个字符串的算法。对于 2 个字符串(小输入)，我逐个字符地比较字符串并进行操作以使它们相等。但是，这种方法对于大量输入会超时。

有人可以解释一下他们使用的算法吗？我可以看到其他用户的解决方案，但无法弄清楚他们做了什么。

Answer 1

我可以告诉您我的解决方案，它适用于小型和大型输入。 首先，我们必须看看是否有解决方案，您可以通过将所有字符串转换为“最简单”的形式来实现。如果其中任何一个不匹配，则没有解决方案。

例如

aaabbbc => abc
abbbbbcc => abc
abbcca => abca

如果只给出前两个，那么解决方案是可能的。一旦第三个被扔进去，那就不可能了。进行“简化”的算法是解析字符串并消除您看到的任何双字符。一旦字符串不等于批处理的简化形式，就退出。

至于问题的实际解决方案，我只是将字符串转换为 [字母，重复] 格式。例如

qwerty => 1q,1w,1e,1r,1t,1y
qqqwweeertttyy => 3q,2w,3e,1r,3t,2y

(请注意，输出是内部结构，而不是实际的字符串)

想象一下，现在您有 100 个字符串，您已经通过了存在解决方案的测试，并且您将所有字符串都放入了 [letter, repeat] 表示中。现在检查每一个字母，找到你必须做的重复的最小“差异”，以达到相同的数字。例如

1a, 1a, 1a => 0 diff
1a, 2a, 2a => 1 diff
1a, 3a, 10a => 9 diff (to bring everything to 3)

执行此操作的方法(我很确定有更有效的方法)是从最小数到最大数并计算所有差异的总和。您不能保证该号码将是集合中的号码之一。对于最后一个示例，您将计算 diff 以使所有内容都为 1 (0,2,9 =11)，然后为 2 (1,1,8 =10)，为 3 (2,0,7 =9) 和以此类推，直到 10，然后再次选择最小值。字符串限制为 1000 个字符，因此这是一个简单的计算。在我的中型笔记本电脑上，结果立竿见影。

对字符串的每个字母重复相同的操作，然后将所有内容加起来，这就是您的解决方案。