减少字符串-编程竞赛。需要的解决方案 [英] String Reduction - Programming Contest . Solution needed

问题描述

我有一个问题，要求我们按如下所示减少字符串。

I have a question which asks us to reduce the string as follows.

输入是仅具有<$ c $的字符串c> A ， B 或 C 。输出的长度必须为缩略字符串
的长度

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.

例如 ABA -> CA -> B 。所以最终答案是1（字符串的长度减少）

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

例如 ABCCCCCCC

这不会成为 CCCCCCCC ，因为它可以通过以下方式减少

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

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

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

，因为这里的长度是2< （ CCCCCCCC 的长度）

as here length is 2 < (length of CCCCCCCC)

您如何处理此问题？

非常感谢！

要弄清楚：问题指出，它要求减法器的最小长度串。因此，在上面的第二个示例中，有2种可能的解决方案，一个 CCCCCCCC 和另一个 AA 。所以2是答案，因为 AA 的长度为2，小于 CCCCCCCC = 8的长度。

To make things clear: the question states it wants the minimum length of the reduced string. So in the second example above there are 2 solutions possible, one CCCCCCCC and the other AA. So 2 is the answer as length of AA is 2 which is smaller than the length of CCCCCCCC = 8.

推荐答案

我假设您正在寻找在归约后可获得的最短字符串的长度。

I'm assuming that you are looking for the length of the shortest possible string that can be obtained after reduction.

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

A simple solution would be to explore all possibilities in a greedy manner and hope that it does not explode exponentially. I'm gonna write Python pseudocode here because that's easier to comprehend (at least for me ;)):

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 应该就可以了），将字符串添加到其中，然后在所有可能的归约空间内进行简单的广度优先搜索。在搜索过程中，您从队列中获取第一个元素，获取其所有可能的子字符串，执行所有可能的归约，然后将归约的字符串推回到队列中。当队列为空时，将浏览整个空间。

I think the basic idea is clear: you take a queue (std::deque should be just fine), add your string into it, and then implement a simple breadth first search in the space of all possible reductions. During the search, you take the first element from the queue, take all possible substrings of it, execute all possible reductions, and push the reduced strings back to the queue. The entire space is explored when the queue becomes empty.

这篇关于减少字符串-编程竞赛。需要的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！