8

我正在为周一的面试做准备，我发现这个问题需要解决，称为“字符串缩减”。问题是这样表述的：

给定一个由 a、b 和 c 组成的字符串，我们可以执行以下操作：取任意两个相邻的不同字符并将其替换为第三个字符。例如，如果“a”和“c”相邻，则可以将它们替换为“b”。通过重复应用此操作可以产生的最小字符串是多少？

例如，cab -> cc 或 cab -> bb，产生长度为 2 的字符串。对于这个，一个最佳解决方案是：bcab -> aab -> ac -> b。不能再进行任何操作，结果字符串的长度为 1。如果字符串 = CCCCC，则不能执行任何操作，因此答案为 5。

我在stackoverflow上看到了很多问题和答案，但我想验证我自己的算法。这是我的伪代码算法。在我的代码中

  1. S是我要减少的字符串
  2. S[i] 是索引 i 处的字符
  3. P 是一个堆栈：

  4. redux 是减少字符的函数。

    function reduction(S[1..n]){        
P = create_empty_stack();
for i = 1 to n
do
   car = S[i];
   while (notEmpty(P))
   do
      head = peek(p);
      if( head == car) break;
      else {
         popped = pop(P);
         car = redux (car, popped);
       }  
   done
   push(car)
done
return size(P)}

我的算法的最坏情况是 O(n)，因为堆栈 P 上的所有操作都在 O(1) 上。我在上面的例子中尝试了这个算法，我得到了预期的答案。让我用这个例子“ abacbcaa ”执行我的算法：

i = 1 :
   car = S[i] = a, P = {∅}
   P is empty, P = P U {car} -> P = {a}

 i = 2 :
   car = S[i] = b, P = {a}
   P is not empty :
       head = a
       head != car ->
            popped = Pop(P) = a 
            car = reduction (car, popped) = reduction (a,b) = c
            P = {∅}

    push(car, P) -> P = {c}



i = 3 :
   car = S[i] = a, P = {c}
   P is not empty :
       head = c
       head != car ->
            popped = Pop(P) = c 
            car = reduction (car, popped) = reduction (a,c) = b
            P = {∅}

    push(car, P) -> P = {b}


 ...


 i = 5 : (interesting case)
  car = S[i] = c, P = {c}
   P is not empty :
       head = c
       head == car -> break

    push(car, P) -> P = {c, c}


 i = 6 :
  car = S[i] = b, P = {c, c}
   P is not empty :
       head = c
       head != car ->
            popped = Pop(P) = c 
            car = reduction (car, popped) = reduction (b,c) = a
            P = {c}

   P is not empty : // (note in this case car = a)
       head = c
       head != car ->
            popped = Pop(P) = c 
            car = reduction (car, popped) = reduction (a,c) = b
            P = {∅}
    push(car, P) -> P = {b}

... and it continues until n

我已经在这样的各种示例上运行了这个算法，它似乎有效。我用 Java 编写了一个测试该算法的代码，当我将代码提交给系统时，我得到了错误的答案。我已经在gisthub上发布了 java 代码， 所以你可以看到它。

有人能告诉我我的算法有什么问题吗？

4

2 回答 2

5

我将尝试解释什么nhahtdh意思。您的算法失败的原因有多种。但最基本的一点是，在每个时间点，只有观察到的第一个字符才有机会被压入堆栈p。不应该这样，因为您基本上可以从任何位置开始减少。

让我给你字符串 abcc。如果我在断点

car = S[i];

算法运行为：

p = {∅}, s = _abcc //underscore is the position
p = {a}, s = a_bcc  
p = {c}, s = ab_cc

在这一点上，你被困在减少ccc

但还有另一个减少：abcc -> aac ->ab ->c

此外，返回堆栈的大小P是错误的。cc不能减少，但算法会返回1。您还应该计算跳过的次数。

于 2012-05-26T14:20:08.910 回答
0

你也可以使用蛮力解决这个问题......和递归

for all n-1 pairs(2 char) replace it with 3rd char if possible and apply reduce on this new string of length n-1
    for all n-2 pairs replace it with 3rd char and apply reduce on new string
         for all n-3 pairs....and so on

长度为 n-1 的新字符串将有 n-2 对，类似地，长度为 n-2 的新字符串将有 n-3 对。

在应用这种方法时，继续存储最小值

if (new_min < min)
    min = new_min

实施：http: //justprogrammng.blogspot.com/2012/06/interviewstreet-challenge-string.html

于 2012-06-13T09:33:15.880 回答