减少字符串 - 编程竞赛.解决方案需要

Question

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

输入是仅具有一个字符串A,B或C.输出必须是缩减字符串的长度

可以通过以下规则减少字符串

如果任何2个不同的字母相邻,则这两个字母可以用第三个字母代替.

例如 ABA- > CA- > B.所以最终答案是1(减少字符串的长度)

例如 ABCCCCCCC

这不会变成CCCCCCCC,因为它可以减少

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

因为这里长度是2 <(长度CCCCCCCC)

你怎么解决这个问题？

非常感谢!

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

Answer 1

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

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

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

编辑:作为概念证明的一种方式,这里是一些语法及其扩展:我应该注意到,虽然这似乎是一个合理的证据,证明长度将减少到1或2,我有理由相信确定哪个这些长度的结果并不像我原先想的那样微不足道(你仍然需要通过所有选项来解决它)

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

where()表示空字符串,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.

Answer 2

您可以根据字符串的单个字符数来概括结果.算法如下,

遍历字符串并获取单个字符计数.

让我们说如果

• a =没有给定字符串中的a的#
• b =没有给定字符串中的b的#
• c =没有给定字符串中的c的#

然后你可以说,结果将是,

if((a == 0 && b == 0 && c == 0) ||
   (a == 0 && b == 0 && c != 0) ||
   (a == 0 && b != 0 && c == 0) ||
   (a != 0 && b == 0 && c == 0))
{
    result = a+b+c;
}
else if(a != 0 && b != 0 && c != 0)
{
    if((a%2 == 0 && b%2 == 0 && c%2 == 0) ||
       (a%2 == 1 && b%2 == 1 && c%2 == 1))
        result = 2;
    else
        result = 1;
}
else if((a == 0 && b != 0 && c != 0) || 
        (a != 0 && b == 0 && c != 0) || 
        (a != 0 && b != 0 && c == 0))
{
    if(a%2 == 0 && b%2 == 0 && c%2 == 0)
        result = 2;
    else
        result = 1;
}

Answer 3

我假设您正在寻找减少后可以获得的最短可能字符串的长度。

一个简单的解决方案是以贪婪的方式探索所有可能性，并希望它不会呈指数爆炸。我将在这里编写 Python 伪代码，因为这样更容易理解（至少对我来说是这样；））：

from collections import deque

def try_reduce(string):
    queue = deque([string])
    min_length = len(string)
    while queue:
        string = queue.popleft()
        if len(string) < min_length:
            min_length = len(string)
        for i in xrange(len(string)-1):
            substring = string[i:(i+2)]
            if substring == "AB" or substring == "BA":
                queue.append(string[:i] + "C" + string[(i+2):])
            elif substring == "BC" or substring == "CB":
                queue.append(string[:i] + "A" + string[(i+2):])
            elif substring == "AC" or substring == "CA":
                queue.append(string[:i] + "B" + string[(i+2):])
    return min_length

我认为基本思想很明确：您采用一个队列（std::deque应该没问题），将字符串添加到其中，然后在所有可能的缩减空间中实现简单的广度优先搜索。在搜索过程中，您从队列中取出第一个元素，取出它的所有可能的子字符串，执行所有可能的缩减，并将缩减后的字符串推回队列。当队列变空时，整个空间都会被探索。