2

我正在尝试在 SPOJ 上解决这个问题：http ://www.spoj.pl/problems/EDIT/

我试图得到一个体面的算法递归描述，但我失败了，因为我的想法一直在转圈！你们能帮我解决这个问题吗？我将尝试描述我试图解决这个问题的方法。

基本上我想解决一个大小为 ji 的问题，其中 i 是起始索引，j 是结束索引。现在，应该有两种情况。如果 ji 是偶数，那么开头和结尾的字母必须是相同的大小写，当 ji 是奇数时，它们必须是相反的大小写。我也想减少较小规模的问题（ji-1 或 ji-2），但我觉得如果我知道较小问题的解决方案，那么构建一个更大问题的解决方案也应该考虑到较小问题的开始和结束字母大小写。这正是我感到困惑的地方。你们能把我的想法放在正确的轨道上吗？

4

3 回答 3

3

我认为递归不是解决这个问题的最佳方法。如果我们采取不同的方法，它可以很快解决！

让我们考虑二进制字符串。假设大写字符为1，小写字符为0。例如

AaAaB -> 10101
ABaa  -> 1100
a     -> 0

“正确”的交替链是10101010 .. 或010101010 ..

我们将一个字符串更改为另一个字符串所需的最小替换次数称为字符串之间的汉明距离。我们要找到的是输入二进制字符串与两个相同长度的交替链之一之间的最小汉明距离。

这并不难：我们对每个字符串进行异或运算，然后计算 1 的数量。（链接）。例如，让我们考虑以下字符串：ABaa。

  • 我们将其转换为二进制：

    ABaa -> 1100

  • 我们生成了仅有的两个长度为 4 的交替链：

    1010

    0101

  • 我们将它们与输入进行异或：

    1100 异或 1010 = 0101

    1100 异或 0101 = 1010

  • 我们计算结果中的 1 并取最小值。在这种情况下，它是2。

我用 Java 编写了这个过程，做了一些小的优化（缓冲 I/O，不需要生成交替链），它被接受了：（0.60 秒）。

在此处输入图像描述

于 2012-09-16T13:40:46.530 回答
1

给定任何长度为 n 的字符串 s，只有两个可能的“交替链”。这两个变体可以通过设置第一个字母状态来顺序定义（如果第一个是上，那么第二个是下，第三个是上......）。

一个简单的线性算法是对第一个字母做两个简单的假设：

  1. 第一个字母是大写
  2. 第一个字母是小写

对于每个假设，运行一个简单的编辑距离算法，你就完成了。

于 2012-09-16T10:51:48.137 回答
1

您可以递归地执行此操作，但是您需要在函数之间传递和返回大量状态信息，当这个问题可以通过一个简单的循环来解决时，我认为这是不值得的。

正如其他人所说，有两种可能的“期望结果”字符串：一种以大写字母开头（我们称之为 result_U），另一种以小写字母开头（result_L）。我们想要 EditDistance(input, result_U) 和 EditDistance(input, result_L) 中较小的一个。

还要注意，要计算 EditDistance(input, result_U)，我们不需要生成 result_U，我们只需要一次扫描输入 1 个字符，每个不是预期大小写的字符都需要 1 次编辑才能使其成为正确的情况，即在编辑距离上加 1。EditDistance（输入，result_L）同上。

此外，我们可以组合这两个循环，以便我们只扫描一次输入。事实上，这可以在读取每个输入字符串时完成。一种天真的方法如下所示：

伪代码：

EditDistance_U = 0
EditDistance_L = 0

Read a character
To arrive at result_U, does this character need editing?
  Yes => EditDistance_U += 1
  No  => Do nothing
To arrive at result_L, does this character need editing?
  Yes => EditDistance_L += 1
  No  => Do nothing
Loop until end of string
EditDistance = min(EditDistance_U, EditDistance_L)

也可以对上述内容进行明显的优化，但我会把它留给你。

提示 1：循环中真的需要 2 个条件吗？它们是如何相互关联的？

提示 2：什么是 EditDistance_U + EditDistance_L？

于 2012-09-16T15:17:53.823 回答