# 算法题：递归删除所有相邻的重复项

2021年4月18日19:05:25 发表评论 1,104 次浏览

## 本文概述

• 从最左边的字符开始, 如果有重复, 请删除左上角的重复项。
• 第一个字符必须与现在的第一个字符不同。重复长度为n-1的字符串(不包含第一个字符的字符串)。
• 令减少长度为n-1的右子字符串后获得的字符串为rem_str。有三种可能的情况
1. 如果是第一个字符rem_str与原始字符串的第一个字符匹配, 从中删除第一个字符rem_str.
2. 如果剩余的字符串为空, 并且最后删除的字符与原始字符串的第一个字符相同。返回空字符串。
3. 否则, 将原始字符串的第一个字符添加到rem_str.
• 返回rem_str.

## C++

``````//C/C++ program to remove all
#include <iostream>
#include <string.h>

using namespace std;

//duplicates from str and returns
//new string. las_removed is a
//pointer to last_removed character
char * removeUtil( char *str, char *last_removed)
{

//If length of string is 1 or 0
if (str[0] == '\0' || str[1] == '\0' )
return str;

//Remove leftmost same characters
//and recur for remaining
//string
if (str[0] == str[1])
{
*last_removed = str[0];
while (str[1] && str[0] == str[1])
str++;
str++;
return removeUtil(str, last_removed);
}

//At this point, the first character
//is definiotely different
//character and recursively
//remove characters from remaining string
char * rem_str = removeUtil(str+1, last_removed);

//Check if the first character
//of the rem_string matches with
//the first character of the
//original string
if (rem_str[0] && rem_str[0] == str[0])
{
*last_removed = str[0];

//Remove first character
return (rem_str+1);
}

//If remaining string becomes
//empty and last removed character
//is same as first character of
//original string. This is needed
//for a string like "acbbcddc"
if (rem_str[0] == '\0' &&
*last_removed == str[0])
return rem_str;

//If the two first characters
//of str and rem_str don't match, //append first character of str
//before the first character of
//rem_str.
rem_str--;
rem_str[0] = str[0];
return rem_str;
}

//Function to remove
char * remove ( char *str)
{
char last_removed = '\0' ;
return removeUtil(str, &last_removed);
}

//Driver program to test
//above functions
int main()
{
char str1[] = "geeksforgeeg" ;
cout <<remove (str1) <<endl;

char str2[] = "azxxxzy" ;
cout <<remove (str2) <<endl;

char str3[] = "caaabbbaac" ;
cout <<remove (str3) <<endl;

char str4[] = "gghhg" ;
cout <<remove (str4) <<endl;

char str5[] = "aaaacddddcappp" ;
cout <<remove (str5) <<endl;

char str6[] = "aaaaaaaaaa" ;
cout <<remove (str6) <<endl;

cout <<remove (str7) <<endl;

char str8[] = "acaaabbbacdddd" ;
cout <<remove (str8) <<endl;

char str9[] = "acbbcddc" ;
cout <<remove (str9) <<endl;

return 0;
}``````

## Java

``````//Java program to remove
//from a string
import java.io.*;
import java.util.*;

class GFG
{

// duplicates from str and returns
//new string. las_removed is a
//pointer to last_removed character
static String removeUtil(String str, char last_removed)
{

//If length of string is 1 or 0
if (str.length() == 0 || str.length() == 1 )
return str;

//Remove leftmost same characters
//and recur for remaining
//string
if (str.charAt( 0 ) == str.charAt( 1 ))
{
last_removed = str.charAt( 0 );
while (str.length()> 1 && str.charAt( 0 ) ==
str.charAt( 1 ))
str = str.substring( 1 , str.length());
str = str.substring( 1 , str.length());
return removeUtil(str, last_removed);
}

//At this point, the first
//character is definiotely different
//character and recursively
//remove characters from remaining string
String rem_str = removeUtil(str.substring(
1 , str.length()), last_removed);

//Check if the first character of
//the rem_string matches with
//the first character of the original string
if (rem_str.length() != 0 &&
rem_str.charAt( 0 ) == str.charAt( 0 ))
{
last_removed = str.charAt( 0 );

//Remove first character
return rem_str.substring( 1 , rem_str.length());
}

//If remaining string becomes
//empty and last removed character
//is same as first character of
//original string. This is needed
//for a string like "acbbcddc"
if (rem_str.length() == 0 && last_removed ==
str.charAt( 0 ))
return rem_str;

//If the two first characters
//of str and rem_str don't match, //append first character of str
//before the first character of
//rem_str
return (str.charAt( 0 ) + rem_str);
}

static String remove(String str)
{
char last_removed = '\0' ;
return removeUtil(str, last_removed);
}

//Driver code
public static void main(String args[])
{
String str1 = "geeksforgeeg" ;
System.out.println(remove(str1));

String str2 = "azxxxzy" ;
System.out.println(remove(str2));

String str3 = "caaabbbaac" ;
System.out.println(remove(str3));

String str4 = "gghhg" ;
System.out.println(remove(str4));

String str5 = "aaaacddddcappp" ;
System.out.println(remove(str5));

String str6 = "aaaaaaaaaa" ;
System.out.println(remove(str6));

System.out.println(remove(str7));

String str8 = "acaaabbbacdddd" ;
System.out.println(remove(str8));
}
}

//This code is contibuted by rachana soma``````

## python

``````# Python program to remove
# all adjacent duplicates from a string

# duplicates from str and returns
# new string. las_removed is a
# pointer to last_removed character
def removeUtil(string, last_removed):

# If length of string is 1 or 0
if len (string) = = 0 or len (string) = = 1 :
return string

# Remove leftmost same characters
# and recur for remaining
# string
if string[ 0 ] = = string[ 1 ]:
last_removed = ord (string[ 0 ])
while len (string)> 1 and string[ 0 ] = =
string[ 1 ]:
string = string[ 1 :]
string = string[ 1 :]

return removeUtil(string, last_removed)

# At this point, the first
# character is definiotely different
# from its adjacent. Ignore first
# character and recursively
# remove characters from remaining string
rem_str = removeUtil(string[ 1 :], last_removed)

# Check if the first character
# of the rem_string matches
# with the first character of
# the original string
if len (rem_str) ! = 0 and rem_str[ 0 ] = =
string[ 0 ]:
last_removed = ord (string[ 0 ])
return (rem_str[ 1 :])

# If remaining string becomes
# empty and last removed character
# is same as first character of
# original string. This is needed
# for a string like "acbbcddc"
if len (rem_str) = = 0 and last_removed = =
ord (string[ 0 ]):
return rem_str

# If the two first characters of
# str and rem_str don't match, # append first character of str
# before the first character of
# rem_str.
return ([string[ 0 ]] + rem_str)

def remove(string):
last_removed = 0

# Utility functions
def toList(string):
x = []
for i in string:
x.append(i)
return x

def toString(x):
return ''.join(x)

# Driver program
string1 = "geeksforgeeg"
print remove(string1)

string2 = "azxxxzy"
print remove(string2)

string3 = "caaabbbaac"
print remove(string3)

string4 = "gghhg"
print remove(string4)

string5 = "aaaacddddcappp"
print remove(string5)

string6 = "aaaaaaaaaa"
print remove(string6)

print remove(string7)

string8 = "acaaabbbacdddd"
print remove(string8)

string9 = "acbbcddc"
print remove(string9)

# This code is contributed by BHAVYA JAIN``````

``````gksfor
ay

g
a

qrq
acac
a``````

## Java

``````//Java Program for above approach
import java.util.*;
import java.lang.*;
import java.io.*;

class GFG
{

//duplicates from str and
//returns new string. las_removed
//is a pointer to
//last_removed character
private static String removeDuplicates(
String s, char ch)
{

//If length of string is 1 or 0
if (s == null || s.length() <= 1 )
{
return s;
}

int i = 0 ;
while (i <s.length())
{
if (i + 1 <s.length()
&& s.charAt(i) == s.charAt(i + 1 ))
{
int j = i;
while (j + 1 <s.length()
&& s.charAt(j) ==
s.charAt(j + 1 ))
{
j++;
}
char lastChar
= i> 0 ? s.charAt(i - 1 ) : ch;

String remStr = removeDuplicates(
s.substring(j + 1 , s.length()), lastChar);

s = s.substring( 0 , i);
int k = s.length(), l = 0 ;

//characters formed by removing the
while (remStr.length()> 0 &&
s.length()> 0 &&
remStr.charAt( 0 ) ==
s.charAt(s.length() - 1 ))
{

//Have to check whether this is the
//repeated character that matches the
//last char of the parent String
while (remStr.length()> 0
&& remStr.charAt( 0 ) != ch
&& remStr.charAt( 0 )
== s.charAt(s.length()
- 1 ))
{
remStr = remStr.substring(
1 , remStr.length());
}
s = s.substring( 0 , s.length() - 1 );
}
s = s + remStr;
i = j;
}
else
{
i++;
}
}
return s;
}

//Driver Code
public static void main(String[] args)
{

String str1 = "mississipie" ;
System.out.println(removeDuplicates(
str1, ' ' ));
String str2 = "ocvvcolop" ;
System.out.println(removeDuplicates(
str2, ' ' ));
}
}

//This code is contibuted by Niharika Sahai``````

``````mpie
lop``````