recursion - 字符串缩减-编程竞赛。需要解决方案

Question

我有一个问题要求我们按如下方式减少字符串。

The input is a string having only A, B or C. Output must be length of the reduced string

The string can be reduced by the following rules

If any 2 different letters are adjacent, these two letters can be replaced by the third letter.

Eg ABA -> CA -> B . So final answer is 1 (length of reduced string)

Eg ABCCCCCCC

This doesn't become CCCCCCCC, as it can be reduced alternatively by

ABCCCCCCC->AACCCCCC->ABCCCCC->AACCCC->ABCCC->AACC->ABC->AA

as here length is 2 < (length of CCCCCCCC)

你是如何解决这个问题的？

非常感谢!

为了清楚起见:问题表明它想要减少字符串的最小长度。所以在上面的第二个例子中有两种可能的解决方案，一种是CCCCCCCC，另一种是AA。所以 2 是答案，因为 AA 的长度是 2，小于 CCCCCCCC 的长度 = 8。

Answer 1

这个问题的措辞方式，只有三种不同的可能性:

1. 如果字符串只有一个唯一字符，则长度与字符串的长度相同。

2/3。如果字符串包含多个唯一字符，则长度始终为 1 或 2(基于字符的布局)。

编辑: 作为概念证明的一种方式，这里有一些语法及其扩展: 我应该注意到，尽管在我看来这似乎是长度将减少到 1 或 2 这一事实的合理证据，但我有理由相信确定这些长度中的哪一个会产生并不像我最初想象的那么微不足道(你仍然会必须遍历所有选项才能找到它)

S   :   A|B|C|()
S   :   S^

其中()表示空串，s^表示前面[A,B,C,()]个字符的任意组合。

扩展语法:

S_1 :   AS^|others
S_2 :   AAS^|ABS^|ACS^|others
S_3 :   AAAS^|
        AABS^ => ACS^ => BS^|
        AACS^ => ABS^ => CS^|
        ABAS^ => ACS^ => BS^|
        ABBS^ => CBS^ => AS^|
        ABCS^ => CCS^ | AAS^|
        ACAS^ => ABS^ => CS^|
        ACBS^ => AAS^ | BBS^|
        ACCS^ => BCS^ => AS^|

以 B 和 C(其他)开头的扩展语法也会发生同样的事情。有趣的情况是我们有 ACB 和 ABC(三个不同的字符顺序)，这些情况导致语法似乎导致更长的长度:

CCS^:   CCAS^|CCBS^|CCCS^|
        CBS^ => AS^|
        CAS^ => BS^|
        CCCS^|
AAS^:   AAAS^|AABS^|AACS^|
        ACS^ => BS^|
        ABS^ => CS^|
        AAAS^|
BBS^:   BBAS^|BBBS^|BBCS^|
        BCS^ => AS^|
        BAS^ => CS^|
        BBBS^|

递归地，当剩余字符串仅包含它们的值时，它们只会导致更长的长度。但是我们必须记住，这种情况也可以简化，因为如果我们用 CCCS^ 到达这个区域，那么我们之前有一个点是 ABC(或因此是 CBA)。如果我们回顾过去，我们本可以做出更好的决定:

ABCCS^  =>  AACS^   =>  ABS^    =>  CS^ 
CBACS^  =>  CBBS^   =>  ABS^    =>  CS^

所以在最好的情况下，当我们做出所有正确的决定时，在字符串的末尾，我们以剩余的 1 个字符的字符串结束，后跟 1 个字符(因为我们在末尾)。此时如果字符相同，则长度为2，如果不同，则最后减1，最后长度为1。