11

我从 interviewstreet.com 看到了各种讨论和尝试解决“字符串缩减”问题的代码，但没有一个是通过动态编程来解决的。

列在动态规划部分下，问题描述如下：

给定一个由 a、b 和 c 组成的字符串，我们可以执行以下操作：取任意两个相邻的不同字符并将其替换为第三个字符。例如，如果“a”和“c”相邻，则可以将它们替换为“b”。

通过重复应用此操作可以产生的最小字符串是多少？

可以使用穷举蛮力搜索来解决该问题，有效地创建所有可能替换的树：

// this is more or less pseudo code from my head
int GetMinLength(string s)
{
    // solve edge cases
    if (s.Length == 1) return 1;
    if (s.Length == 2) return ReduceIfPossible(s);

    // recursive brute force
    int min = s.Length;
    for (int i = 0; i<s.Length-1; i++)
    {
        if (s[i] != s[i+1])
        {
            var next = GetMinLength(
                  s.Substring(0, i) + 
                  Reduce(s[i], s[i + 1]) +
                  s.Substring(i + 2)
                  );

            if (next < min) min = next;
        }
    }
}

N对于较大的( )，这显然会失败N <= 100，因此我试图将其分解为较小的子问题，记忆它们并合并结果。

问题是我无法确定具有“最佳子结构”的状态，需要应用动态编程（或者换句话说，“合并”子问题的结果）。最小化字符串的一部分并不能保证最终的字符串确实是最小的解决方案。

在这种情况下，可以合并到最终解决方案的子问题“状态”是什么？

4

3 回答 3

1

使这变得棘手的是，您需要将其视为连续的 2 个动态编程问题。

  1. 建立一个表格，按您结束的字符，按开始位置，所有可能的结束位置，这些位置是可以简化为该字符的块。
  2. i字符串的最后一个字符可以减少到的最小长度。（您在步骤 1 中构建的表可用于递归地将此问题简化为已解决的子问题。）

第二个提供你的答案。如果你已经解决了第一个问题，那就更简单了。

于 2012-06-28T14:49:33.257 回答
1

剧透警报代码：

public static int findMinReduction(String line){
    //Pseudocode:
    //Count the number of occurences of each letter in the input string.
    //If two of these counts are 0, then return string.length
    //Else if (all counts are even) or (all counts are odd), then return 2
    //Else, then return 1

    int len = line.length();
    String a_reduce = line.replaceAll("c", "").replaceAll("b", "");
    String b_reduce = line.replaceAll("a", "").replaceAll("c", "");
    String c_reduce = line.replaceAll("a", "").replaceAll("b", "");

    int a_occurances = a_reduce.length();
    int b_occurances = b_reduce.length();
    int c_occurances = c_reduce.length();

    if ((a_occurances == b_occurances && a_occurances == 0) || 
       (a_occurances == c_occurances && a_occurances == 0) || 
       (b_occurances == c_occurances && b_occurances == 0)){
        return len;
    }
    else{
        if (a_occurances % 2 == 0 && 
            b_occurances % 2 == 0 && 
            c_occurances % 2 == 0){
            return 2;
        }
        if (a_occurances % 2 != 0 
            && b_occurances % 2 != 0 && 
            c_occurances % 2 != 0){
            return 2;
        }
    }
    return 1;
}

复杂：

这是一个 O(n) 时间复杂度操作，随着输入大小的增加，要完成的工作量与输入大小成线性关系。这是闪电般的速度，我们可以处理兆字节大小的字符串，并且仍然可以在几分之一秒内处理它们。

在这里找到的算法，全面分析了该算法的工作原理：

被Java面试难住了，需要一些提示

于 2015-09-30T21:50:08.850 回答
0

您首先创建一个描述解决方案理论的结构。它包括考虑的字符数，到目前为止的编码字符串，以及理论的最坏情况和最佳情况。

一开始只有一个理论——没有处理任何字符。最好的情况是长度为 1 的字符串（例如，规则始终适用，字符串可以缩减为一个字符，最坏的情况是 N，没有规则适用）例如

encoded string = "";
encoded index = 0;
worst case = N; 
best case = 1;

现在开始将索引加一，并将一个字符添加到编码的字符串中。如果没有适用的规则，你就保持这个理论不变。如果某个规则确实适用，您必须做出决定——要么应用该规则，要么不应用该规则。因此，当您添加一个角色时，您会复制适用于最后一个角色的每条规则的理论，并为没有应用任何规则保留一个版本。你更新每个理论的最佳情况和最坏情况。

起初，理论的数量会迅速增加。但最终你会遇到这样一种情况，即某些理论的最坏情况优于其他理论的最佳情况。

因此，每当您推进索引时，您都会删除最佳情况比具有最佳最坏情况的理论更差的理论。随着指数接近 N，大多数理论将退出。

于 2012-06-28T18:09:51.330 回答