解决字符串缩减算法

Question

我正在为周一的面试做准备，发现了一个需要解决的问题，名为 "String Reduction"。该问题陈述如下：

给定一个由a、b和c组成的字符串，我们可以执行以下操作：取任意两个相邻且不同的字符，并用第三个字符替换它。例如，如果'a'和'c'相邻，则可以用'b'替换它们。通过重复应用此操作，得到最小的字符串是什么？

例如，cab -> cc或cab -> bb，结果为长度为2的字符串。对于这个问题，一个最优解是：bcab -> aab -> ac -> b。不能再应用更多操作，而且结果字符串的长度为1。 如果字符串=C CCCC，则无法执行任何操作，因此答案是5。

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

1. S is my string to reduce
2. S[i] is the character at index i
3. P is a stack:

4. redux is the function that reduces the characters.

   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代码，这样你就可以看到它。

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

- Dimitri

---

它正在要求最小的字符串，那么如果有多种减少字符串的方法，你必须找到它。你似乎只搜索第一种减少的方式，当然，这样会失败。有时，不使用规则并等待更多字符到来可能会得到更好的结果。 - nhahtdh

@acattle 是的，但只在第一种情况下，即第一个字符。在每个for循环中，堆栈至少会有一个字符。 - Dimitri

@nhahtdh，你能具体说明一下吗？ - Dimitri

我认为不可能获得一个 O(n) 的算法... - UmNyobe

这个简单的算法可能会很有用http://jsfiddle.net/YFw4G/，JavaScript易于理解。 - ajax333221

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。您还应计算跳过次数。

- UmNyobe

---

不行，你需要涵盖所有情况。对于给定大小为n的字符串，天真地说，有n-1个redux导致n-1个大小为n-1的字符串。这导致了n！的复杂度，这是灾难性的。必须有一种方法（动态规划等）来减少这种复杂性。 - UmNyobe

Answer 2

你也可以使用暴力算法和递归来解决这个问题。

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

- sachin