Рубрики

Рекурсивно удалить все смежные дубликаты

По заданной строке рекурсивно удаляйте соседние повторяющиеся символы из строки. Выходная строка не должна иметь соседних дубликатов. Смотрите следующие примеры.

Примеры :

Input: azxxzy
Output: ay
First “azxxzy” is reduced to “azzy”.
The string “azzy” contains duplicates,
so it is further reduced to “ay”.

Input: geeksforgeeg
Output: gksfor
First “geeksforgeeg” is reduced to
“gksforgg”. The string “gksforgg”
contains duplicates, so it is further
reduced to “gksfor”.

Input: caaabbbaacdddd
Output: Empty String

Input: acaaabbbacdddd
Output: acac

Можно использовать следующий подход для удаления дубликатов за время O (N) :

  • Начните с самого левого символа и удалите дубликаты в левом углу, если они есть.
  • Первый символ должен отличаться от соседних сейчас. Recur для строки длиной n-1 (строка без первого символа).
  • Пусть строка, полученная после уменьшения правой подстроки длины n-1, будет rem_str . Есть три возможных случая
    1. Если первый символ rem_str совпадает с первым символом исходной строки, удалите первый символ из rem_str .
    2. Если оставшаяся строка становится пустой, а последний удаленный символ совпадает с первым символом исходной строки. Вернуть пустую строку.
    3. Иначе, добавьте первый символ исходной строки в начале rem_str .
  • Вернуть rem_str .

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// C / C ++ программа для удаления всех соседних дубликатов из строки
#include <iostream>
#include <string.h>

  

using namespace std;

  
// Рекурсивно удаляет соседние дубликаты из str и возвращает
// новая строка. las_removed - указатель на символ last_removed

char* removeUtil(char *str, char *last_removed)

{

    // Если длина строки равна 1 или 0

    if (str[0] == '\0' || str[1] == '\0')

        return str;

  

    // Удалить крайние левые символы и повторить оставшиеся

    // строка

    if (str[0] == str[1])

    {

        *last_removed = str[0];

        while (str[1] && str[0] == str[1])

            str++;

        str++;

        return removeUtil(str, last_removed);

    }

  

    // На этом этапе первый символ определенно отличается

    // из соседних. Игнорировать первый символ и рекурсивно

    // удаляем символы из оставшейся строки

    char* rem_str = removeUtil(str+1, last_removed);

  

    // Проверяем, соответствует ли первый символ строки rem_string

    // первый символ исходной строки

    if (rem_str[0] && rem_str[0] == str[0])

    {

        *last_removed = str[0];

        return (rem_str+1); // Удалить первый символ

    }

  

    // Если оставшаяся строка становится пустой и последний удаленный символ

    // совпадает с первым символом исходной строки. Это нужно

    // для строки типа "acbbcddc"

    if (rem_str[0] == '\0' && *last_removed == str[0])

        return rem_str;

  

    // Если два первых символа str и rem_str не совпадают,

    // добавляем первый символ строки перед первым символом

    // rem_str.

    rem_str--;

    rem_str[0] = str[0];

    return rem_str;

}

  

char *remove(char *str)

{

    char last_removed = '\0';

    return removeUtil(str, &last_removed);

}

  
// Программа драйвера для проверки вышеуказанных функций

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-программа для удаления всех смежных дубликатов
// из строки

import java.io.*;

import java.util.*;

  

class GFG {

      // Рекурсивно удаляет соседние дубликаты из str и возвращает

      // новая строка. las_removed - указатель на символ last_removed

      static String removeUtil(String str, char last_removed)

      {

             // Если длина строки равна 1 или 0

             if (str.length() == 0 || str.length() == 1)

                 return str;

  

             // Удалить крайние левые символы и повторить оставшиеся

             // строка

             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); 

             }

  

             // На этом этапе первый символ определенно отличается

             // из соседних. Игнорировать первый символ и рекурсивно

             // удаляем символы из оставшейся строки

             String rem_str = removeUtil(str.substring(1,str.length()), last_removed);

  

             // Проверяем, соответствует ли первый символ строки rem_string

             // первый символ исходной строки

             if (rem_str.length() != 0 && rem_str.charAt(0) == str.charAt(0))

             {

                last_removed = str.charAt(0);

                return rem_str.substring(1,rem_str.length()); // Удалить первый символ

             

  

  

             // Если оставшаяся строка становится пустой и последний удаленный символ

             // совпадает с первым символом исходной строки. Это нужно

             // для строки типа "acbbcddc"

             if (rem_str.length() == 0 && last_removed == str.charAt(0))

                 return rem_str;

  

             // Если два первых символа str и rem_str не совпадают,

             // добавляем первый символ строки перед первым символом

             // rem_str

             return (str.charAt(0) + rem_str);

      }

   

      static String remove(String str)  

      {

             char last_removed = '\0';

             return removeUtil(str, last_removed);       

      }

  

      // Код драйвера

      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));

         

      }

}

  
// Этот код поддерживается rachana soma

питон

# Программа Python для удаления всех соседних дубликатов из строки

  
# Рекурсивно удаляет соседние дубликаты из str и возвращает
# новая строка. las_removed - указатель на символ last_removed

def removeUtil(string, last_removed):

  

    # Если длина строки равна 1 или 0

    if len(string) == 0 or len(string) == 1:

        return 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)

  

    # На данный момент, первый персонаж определенно отличается

    # от соседних. Игнорировать первый символ и рекурсивно

    # удалить символы из оставшейся строки

    rem_str = removeUtil(string[1:], last_removed)

  

    # Проверьте, соответствует ли первый символ строки rem_string

    # с первым символом исходной строки

    if len(rem_str) != 0 and rem_str[0] == string[0]:

        last_removed = ord(string[0])

        return (rem_str[1:])

  

    # Если оставшаяся строка становится пустой и последний удаленный символ

    # совпадает с первым символом оригинальной строки. Это нужно

    # для строки типа "acbbcddc"

    if len(rem_str) == 0 and last_removed == ord(string[0]):

        return rem_str

  

    # Если два первых символа str и rem_str не совпадают,

    # добавить первый символ строки перед первым символом

    # rem_str.

    return ([string[0]] + rem_str)

  

def remove(string):

    last_removed = 0

    return toString(removeUtil(toList(string), last_removed))

  
# Сервисные функции

def toList(string):

    x = []

    for i in string:

        x.append(i)

    return x

  

def toString(x):

    return ''.join(x)

  
# Драйверная программа

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)

  
# Этот код предоставлен BHAVYA JAIN


Выход:

gksfor
ay

g
a

qrq
acac
a

Сложность по времени: сложность по времени решения может быть записана как T (n) = T (nk) + O (k), где n — длина входной строки, а k — количество первых символов, которые являются одинаковыми. Решение повторения O (n)

Спасибо Прачи Бодке за предложение этой проблемы и первоначальное решение. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Рекурсивно удалить все смежные дубликаты

0.00 (0%) 0 votes