求解字符串约简算法

Question

我正准备接受我周一的采访,我发现这个问题要解决,称为" 减少字符串 ".问题是这样说的:

给定由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代码, 你可以看到它.

有人可以告诉我我的算法有什么问题.

Answer 1

我将尝试解释什么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.您还应该计算跳过的次数.