本文概述
给定字符串, 以递归的方式从字符串中删除相邻的重复字符。输出字符串不应包含任何相邻的重复项。请参阅以下示例。
例子:
输入：azxxzy
输出：ay
首先将"azxxzy"减小为"azzy"。字符串"azzy"包含重复项, 因此将其进一步简化为"ay"。
输入：geeksforgeeg
输出：gksfor
第一个"geeksforgeeg"被简化为"gksforgg"。字符串"gksforgg"包含重复项, 因此将其进一步简化为"gksfor"。
输入：caaabbbaacdddd
输出：空字符串
输入：acaaabbbacdddd
输出：acac
以下方法可以遵循以删除重复项上)时间：
- 从最左边的字符开始, 如果有重复, 请删除左上角的重复项。
- 第一个字符必须与现在的第一个字符不同。重复长度为n-1的字符串(不包含第一个字符的字符串)。
- 令减少长度为n-1的右子字符串后获得的字符串为rem_str。有三种可能的情况
- 如果是第一个字符rem_str与原始字符串的第一个字符匹配, 从中删除第一个字符rem_str.
- 如果剩余的字符串为空, 并且最后删除的字符与原始字符串的第一个字符相同。返回空字符串。
- 否则, 将原始字符串的第一个字符添加到rem_str.
- 返回rem_str.
下图是上述方法的模拟：
下面是上述方法的实现：
C++
//C/C++ program to remove all
//adjacent duplicates from a string
#include <iostream>
#include <string.h>
using namespace std;
//Recursively removes adjacent
//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
//from its adjacent. Ignore first
//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;
char str7[] = "qpaaaaadaaaaadprq" ;
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
//all adjacent duplicates
//from a string
import java.io.*;
import java.util.*;
class GFG
{
//Recursively removes adjacent
// 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
//from its adjacent. Ignore first
//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));
String str7 = "qpaaaaadaaaaadprq" ;
System.out.println(remove(str7));
String str8 = "acaaabbbacdddd" ;
System.out.println(remove(str8));
}
}
//This code is contibuted by rachana somapython
# Python program to remove
# all adjacent duplicates from a string
# Recursively removes adjacent
# 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
return toString(removeUtil(toList(string), last_removed))
# 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)
string7 = "qpaaaaadaaaaadprq"
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时间复杂度：
解决方案的时间复杂度可以写成T(n)= T(n-k)+ O(k), 其中n是输入字符串的长度, k是相同的第一个字符的数量。递归的解是O(n)
另一种方法：
这里的想法是检查String remStr是否具有与父String的最后一个字符匹配的重复字符。如果发生这种情况, 那么我们必须在连接字符串s和字符串remStr之前继续删除该字符。
下面是上述方法的实现：
Java
//Java Program for above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
//Recursively removes adjacent
//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 ;
//Recursively remove all the adjacent
//characters formed by removing the
//adjacent characters
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时间复杂度：O(n)
建议这个问题和最初的解决方案。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
