算法题（递归删除所有相邻的重复项） _数据结构

本文概述

C++
Java
python
Java

给定字符串, 以递归的方式从字符串中删除相邻的重复字符。输出字符串不应包含任何相邻的重复项。请参阅以下示例。
【算法题（递归删除所有相邻的重复项）】例子:

输入：azxxzy
输出：ay
首先将"azxxzy"减小为"azzy"。字符串"azzy"包含重复项, 因此将其进一步简化为"ay"。
输入：geeksforgeeg
输出：gksfor
第一个"geeksforgeeg"被简化为"gksforgg"。字符串"gksforgg"包含重复项, 因此将其进一步简化为"gksfor"。
输入：caaabbbaacdddd
输出：空字符串
输入：acaaabbbacdddd
输出：acac

以下方法可以遵循以删除重复项上)时间：

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

python

# 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 ayg aqrq 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

输出如下：