Java 如何递归删除所有相邻的重复项

How to recursively remove all adjacent duplicates

提问by AnujKu

I am not able to come up with a best solution ( O(n) time) to recursively remove adjacent duplicates from a string. My attempt :

我无法想出最佳解决方案（O(n) 时间）来递归地从字符串中删除相邻的重复项。我的尝试：

public static String removeDuplicate(String s) {
   if ( s == null ) return null;
   if ( s.length() <= 1 ) return s;
   if( s.substring(1,2).equals(s.substring(0,1))) 
      return removeDuplicate(s.substring(1));
   else return s.substring(0,1) + removeDuplicate(s.substring(1));
}

But it does not work for cases such as :

但它不适用于以下情况：

 "azxxzy" -> "ay"

In above case these are the string transformations :

在上述情况下，这些是字符串转换：

azxxzy azzy ay

azxxzy azzy ay

Sample input outputs :

示例输入输出：

Input: azxxzy Output: ay

输入：azxxzy 输出：ay

Input: caaabbbaacdddd Output: Empty String

输入：caaabbbaacdddd 输出：空字符串

Input: acaaabbbacdddd Output: acac

输入：acaaabbbacdddd 输出：acac

UPDATE

更新

I have posted a version of answer below.

我在下面发布了一个版本的答案。

采纳答案by AnujKu

I came up with this ugly solution with JasonC's idea (and actually my first idea which I did not pursue) of appending the characters to the output and in case there is adjacent duplicate deleting from the output.

我用 JasonC 的想法（实际上是我没有追求的第一个想法）提出了这个丑陋的解决方案，将字符附加到输出中，以防从输出中删除相邻的重复项。

public static String removeDuplicate(String s) {
 StringBuilder builder = new StringBuilder();
 char lastchar = '
public static String removeDuplicates(String s) {
if (s.isEmpty()) {
    return s;
}
char[] buf = s.toCharArray();
char lastchar = buf[0];

// i: index of input char
// o: index of output char
int o = 1;
for (int i = 1; i < buf.length; i++) {
    if (o > 0 && buf[i] == buf[o - 1]) {
        lastchar = buf[o - 1];
        while (o > 0 && buf[o - 1] == lastchar) {
            o--;
        }
    } else if (buf[i] == lastchar) {
        // Don't copy to output
    } else {
        buf[o++] = buf[i];
    }
}
return new String(buf, 0, o);
}
';
 for (int i = 0; i < s.length(); i++) {
   String str = builder.toString();
   if (!str.equals("")
       && (str.charAt(str.length() - 1) == s.charAt(i))) {
     builder.deleteCharAt(str.length() - 1);
   } else if (s.charAt(i) != lastchar)
     builder.append(s.charAt(i));
   lastchar = s.charAt(i);
 }
return builder.toString();
}

UPDATEBut the best solution is : with the help of this

UPDATE但是，最好的解决方法是：用的帮助下这

public static String removeDuplicate(String string) {
    if(string == null) return null;
    return String.copyValueOf(removeDuplicate(string.toCharArray()));
}

public static char[] removeDuplicate(char[] chars) {
    if(chars.length < 1) return new char[0];
    else if(chars.length == 1) return chars;

    for(int i=0; i<chars.length-1; i++) {
        if(chars[i] == chars[i+1]) {
            char[] before = Arrays.copyOfRange(chars, 0, i);
            char[] after = Arrays.copyOfRange(chars, i+2, chars.length);
            char[] combined = new char[before.length + after.length];
            System.arraycopy(before, 0, combined, 0, before.length);
            System.arraycopy(after, 0, combined, before.length, after.length);
            chars = removeDuplicate(combined);
            break;
        }
    }
    return chars;
}

回答by Ghostkeeper

As people in the comments of your question have mentioned, Stringmanipulations are already O(n) since Stringis immutable. This can be solved by using an array of Characters instead. Since you're also removing stuff, you should also use nulls in that array in order to prevent having to move stuff around every time you remove characters. At the end you'll need to make an additional pass over the array to convert it into a string.

正如您问题评论中的人们所提到的，String操作已经是 O(n)，因为它String是不可变的。这可以通过使用Characters数组来解决。由于您还要删除内容，因此您还应该null在该数组中使用s 以防止每次删除字符时都必须移动内容。最后，您需要对数组进行额外的传递以将其转换为字符串。

The real problem you are asking about is simpler. Removing xxfrom a string like azxxzywill put the characters before and after the xxnext to each other, and they may be the same. So simply check for this again: Place the cursor one spot earlier. Continue with the string zzyrather than with zy.

您要问的真正问题更简单。xx从字符串中删除likeazxxzy会将前后的字符放在xx一起，并且它们可能相同。所以只需再次检查一下：将光标提前一个位置。继续使用字符串zzy而不是zy.

The complexity would remain O(n), since every character is checked against at most twice and can be removed at most once.

复杂度将保持为 O(n)，因为每个字符最多检查两次并且最多可以删除一次。

Since you are asking specifically for a recursive answer, I'll assume this is a homework exercise and leave the implementation to you (use that Characterarray and add indices of the starting positions as extra argument to your method). A non-recursive algorithm would be more efficient as well as easier to implement!

由于您专门要求递归答案，因此我将假设这是一项家庭作业并将实现留给您（使用该Character数组并将起始位置的索引添加为您的方法的额外参数）。非递归算法会更有效，也更容易实现！

回答by Yos233

I converted it to a char array. Also I'm not sure how fast this is completed in, but your question didn't seem to stress about the O-time, you just wanted one that worked (if I read your question correctly).

我将其转换为字符数组。此外，我不确定这完成的速度有多快，但您的问题似乎并没有强调 O-time，您只是想要一个有效的（如果我正确阅读了您的问题）。

Converting to a char array means you don't have to work with Strings, which are immutable (so you have to reconstruct them each time you make a change).

转换为 char 数组意味着您不必使用不可变的字符串（因此每次进行更改时都必须重建它们）。

public static void main(String args[]) {
    System.out.println(removeDuplicate("azxxzy"));
    System.out.println(removeDuplicate("Does this have any duplicates?"));
    System.out.println(removeDuplicate("Nfggfoyy frttrfihht dfbllbfoedssssdsnpr''rp'tuiiu"));
}

You can test it with this:

你可以用这个来测试它：

 public class StackDemo {
    public static void main(String[] args) throws Exception {
        CharStackArray stack = new CharStackArray(15);
        char[] dupliactes = { 'a', 'z', 'x', 'x', 'z', 'y' };
        stack.removeAdjacentDuplicate(dupliactes);
    }

}

class CharStackArray {
    private char[] array;
    private int top;
    private int capacity;

    public void removeAdjacentDuplicate(char[] arr) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            if (isEmpty()) { // if stack is empty
                push(arr[i]);
                display();
                System.out.println();
            } else {
                int count = 0;
                int j = i;
                /*
                 * while top of stack is equal to next value in array (ie same
                 * adjacent values)
                 */
                while (j < arr.length && peek() == arr[j]) {
                    count++; // count of same occurences
                    j++;
                }
                if (count == 0) { // no same occurence
                    push(arr[i]); // push to stack
                    display();
                    System.out.println();
                } else {
                    for (int k = 1; k < count; k++) // skip the array index for
                        // same adjacent duplicates
                        i++;
                    pop(); // pop the duplicate value from stack
                    display();
                    System.out.println();

                }
            }

        }
    }

    public CharStackArray(int cap) {
        capacity = cap;
        array = new char[capacity];
        top = -1;
    }

    public void push(char data) {
        array[++top] = data;
    }

    public char pop() throws Exception {
        return array[top--];
    }

    public void display() {
        for (int i = 0; i <= top; i++) {
            System.out.print(array[i] + "->");
        }
    }

    public char peek() throws Exception {
        return array[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }

}

回答by Prateek Joshi

You can also use stackfor this :

您还可以为此使用堆栈：

public class RemoveAdjucentDuplicates {
public static void main(String[] args) {
    String s = "azxxzy";
    s = "geeksforgeeg";
    System.out.println(remove(s));
}

static String remove(String s) {
    char res[] = new char[s.length()];
    int j = 0;
    res[j] = s.charAt(0);
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) != res[j]) {
            res[++j] = s.charAt(i);
        } else {
            res[j--] = '\u0000';
        }
    }

    String result = String.valueOf(res);
    return result.substring(0,j+1);
}
}

OUTPUT:

输出：

a->

一个->

a->z->

a->z->

a->z->x->

a->z->x->

a->z->

a->z->

a->

一个->

a->y->

a->y->

回答by RIPAN

A non recursive simple solution is

一个非递归的简单解决方案是

public class RemoveAdjacant
{
 public String replaceAdjacent(String s)
 {
  if (s.equals(""))
   return s;
  String adjacentString = "";
  char cha;
  int count = 1;
  for (int i = 0; i < s.length(); i++)
  {
   cha = s.charAt(i);
   adjacentString = adjacentString + cha;
   for (int j = 1 + i; j < s.length(); j++)
   {
    if (cha == s.charAt(j))
    {
     adjacentString = adjacentString + cha;
     count++;
    } else
    {
     if (count >= 3)
      break;
     else
     {
      count = 1;
      adjacentString = "";
      break;
     }
    }
   }
   if (count >= 3)
   {
    int index = s.indexOf(adjacentString);
    s = s.substring(0, index)
      + s.substring(index + adjacentString.length());
    return replaceAdjacent(s);
   }
  }
  return s;
 }
 public static void main(String[] args)
 {
  RemoveAdjacant ra = new RemoveAdjacant();
  Scanner scan = new Scanner(System.in);
  System.out.println("Enter string");
  String s = scan.nextLine();
  System.out.println("rem string=" + ra.replaceAdjacent(s));
 }
}

回答by BISHWAJEET

 import java.io.*;
    import java.util.*;
    import java.util.concurrent.TimeUnit;
    import com.google.common.base.Stopwatch;

    /*
     "Given a string, remove the consecutive character pairs repetitively.
    input: saabbs , output : 
    input: aaabbbccc , output : abc"

     */

    class Solution {
      public static String removeDuplicates(String s) {
        int count=0;
        String sout = "";
        if (s.isEmpty() || s.length()==1) {
            return s;
        }
        else{
          s=s+" ";
          for(int i=0; i<s.length()-1;i++){
            if(s.charAt(i)!= s.charAt(i+1) || s.charAt(i+1)==' '){
              sout = sout+s.charAt(i);
            }else{
              count++;
              i=i+1;
            }
          }
        }
        //int count=0;
        for(int i=0; i<sout.length()-1;i++){
          if(sout.charAt(i)==sout.charAt(i+1))
            count++;
        }
        if(count>0){
          return removeDuplicates(sout);
        }else
          return sout;
    }
      public static void main(String[] args) throws IOException{

        Stopwatch timer = Stopwatch.createStarted();
       // String s = "saabbs";
      String s1 = "aaabbbccc";
      //System.out.println("Output1:\t"+removeDuplicates(s));
      System.out.println("Output2:\t"+removeDuplicates(s1));
        timer.stop();
         System.out.printf("Time taken: %,10d microseconds\n", timer.elapsed(TimeUnit.MICROSECONDS));

      }

    }

回答by Avinash Kumar

I guess, It is better to use recursion . Moreover conversion of string to character array also consumes some time. So, I would prefer to go with normal string input.

我想，最好使用递归。此外，字符串到字符数组的转换也需要一些时间。所以，我更愿意使用普通的字符串输入。

My code would somehow look like following( I have used Java 8):

我的代码以某种方式如下所示（我使用了 Java 8）：

package algorithms;

public class Sample {

    public static void main(String args[]){
        new Sample().fix("Whaaaatupducck");
    }

    public void fix(String input){
        StringBuilder sb = new StringBuilder();

        for(int index = 0; index<input.length()-1 ;index++){

            System.out.println("compare "+ 
            input.charAt(index)+                
            " and "+
            input.charAt(index+1));

            if(input.charAt(index) == input.charAt(index+1)){
                continue; // skipping repeats
            }else{
                sb.append(input.charAt(index));
            }

            if((index+2) == input.length()){
                sb.append(input.charAt(index+1)); // handling last character
            }
        }
        System.out.println("Result : "+sb.toString());
    }
}

回答by user7888762

def rmv(st,i):
    if i==len(st)-1:
        return
    if not st:
        return 
    if st[i]==st[i+1]:
        tmp=st[i]
        while(i<len(st) and st[i]==tmp):
            st.pop(i)
        if not i-1:
            rmv(st,i-1)
        else:
            rmv(st,0)
    else:
        rmv(st,i+1)

inp=list("azxxzy")
rmv(inp,0)
print ''.join(inp)

OUTPUT:

输出：

compare W and h| compare h and a| compare a and a| compare a and a| compare a and a| compare a and t| compare t and u| compare u and p| compare p and d| compare d and u| compare u and c| compare c and c| compare c and k|

比较 W 和 h| 比较 h 和 a| 比较a和a| 比较a和a| 比较a和a| 比较a和t| 比较 t 和 u| 比较 u 和 p| 比较 p 和 d| 比较d和u| 比较u和c| 比较 c 和 c| 比较 c 和 k|

Result :

结果 ：

Whatupduck

什么鸭鸭

回答by Vishwanath Hiremath

Here is the simple recursive python solution to remove all adjacent duplicates.

这是删除所有相邻重复项的简单递归python解决方案。

private static String remove(String str1) {
    StringBuilder sb = new StringBuilder();
    Stack<Character> stack = new Stack<Character>();
    stack.push(str1.charAt(0));
    int inx = 1;
    char lastDeleted = '##代码##';
    while(!stack.isEmpty() && inx < str1.length()){
        if(str1.charAt(inx) == stack.peek()) {
            //repeating character found..
            lastDeleted = stack.pop();
        }else if(str1.charAt(inx) == lastDeleted) {
            //repeating character found but already removed from the stack.
        }else {
            //when a new character is introduced..
            stack.push(str1.charAt(inx));
        }
        inx++;
        if(stack.isEmpty() && inx < str1.length()) {
            //if stack is empty, then insert at least one element if present..
            stack.push(str1.charAt(inx));
            inx++;
        }
    }
    if(stack.isEmpty()) {
        return "";
    }else {
        while(!stack.isEmpty()) {
            sb.insert(0, stack.pop());
        }
    }
    return sb.toString();
}

This program prints ayas output.

这个程序打印ay作为输出。

回答by Ambuj Mani Tripathi

Another solution using stack :

使用堆栈的另一种解决方案：

##代码##