Bütün bitişik dublikatları rekursiv şəkildə çıxarın

Bir sətir verildikdə, bitişik bütün dublikatları rekursiv şəkildə silmək üçün bir funksiya yazın.

Məsələn 1

GİRİŞ:
s = “abssbe”

Çıxış:
“Ae”

Yuxarıda göstərilən nümunədə 's' dublikatlarının sətri çıxarıldıqdan sonra "abbe" olur, bu sətir bitişik dublikatları ehtiva edir, buna görə 'b' dublikatlarının çıxarılmasından sonra çıxış sətri "ae" olur

Məsələn 2

GİRİŞ:
s = "adaacad"

Çıxış:
“Adcad”

Zamanın mürəkkəbliyi: O (n ^ 2)

Bu metodda əsas fikir əvvəlcə giriş sətrindən dublikatları silməkdir və əgər çıxış sətrində hər hansı bir dublikat varsa, onları çıxarmaq sətrində dublikatımız olmayana qədər onları təkrarən silmək lazımdır.

Alqoritm

1. Giriş sətrinin bütün unikal simvollarını çıxış sətrinə əlavə edin, əgər giriş sətrinin uzunluğu çıxış sətri ilə eynidirsə, dayandırın, əks halda

2. Çıxış sətrini funksiyaya giriş sətri kimi götürün

C ++ Proqramı

#include <iostream>
#include <string.h>
using namespace std;
 
// This function recursively removes duplicates
// and returns modified string
char* removeAdjDup(char * s, int n)
{
    int i;
    int k = 0; // To store index of result
 
    // Start from second character
    for (i=1; i< n; i++)
    {
        // If the adjacent chars are different
        //then add to output string
        if (s[i-1] != s[i])
            s[k++] = s[i-1];
 
        else
            // Keep skipping (removing) characters
            // while they are same.
            while (s[i-1] == s[i])
                i++;
    }
 
    // Add last character and terminator
    s[k++] = s[i-1];
    s[k] =  '\0';
 
    // Recur for string if there were some removed
    // character
    if (k != n)
        removeAdjDup(s, k);// Shlemial Painter's Algorithm
 
    // If all characters were unique
    else return s;
}
 
int main()
{
    char str1[] = "abssbe";
    cout << removeAdjDup(str1, strlen(str1)) << endl;
 
    char str2[] = "adaaacad";
    cout << removeAdjDup(str2, strlen(str2)) << endl;
 
}

Yoxla

Zaman Mürəkkəbliyi: O (n)

Alqoritm

1. Ən soldakı simvoldan başlayın və sol küncdə hər hansı bir nüsxə varsa, onları silin

2. İndi ilk simvol bitişik simvoldan fərqlənir, qalan uzunluq n-1 sətri üçün təkrarlanır

3. Rekursiv zəngdən sonra bütün dublikatlar qalan sətirdən silinir, onu rem_str adlandırın İndi ilk xarakter və rem_str,

a. Rem_str-in ilk işarəsi orijinal simlin ilk simvolu ilə uyğun gəlirsə, ilk simvolu rem_str-dən silin.

  b. Rekursiv çağırışlarda son silinən simvol orijinal sətrin ilk simvolu ilə eyni olduqda başqa bir halda. Orijinal sətrin ilk simvoluna məhəl qoymayın və rem_str.

c. Başqa bir halda, orijinal simli ilk simvolunu rem_str başında əlavə edin.

4. Geri qayıt rem_str.

C ++ Proqramı

#include <iostream>
#include <string.h>
using namespace std;
 
// Recursively removes adjacent duplicates from s and returns
// new string. last_removed is a pointer to last removed character
char* recRemoveAdjDup(char *s, char *last_removed)
{
    // If length of string is 1 or 0
    if (s[0] == '\0' || s[1] == '\0')
        return s;
 
    // Remove leftmost same characters and recur for remaining 
    // string
    if (s[0] == s[1])
    {
        *last_removed = s[0];
        while (s[1] && s[0] == s[1])
            s++;
        s++;
        return recRemoveAdjDup(s, last_removed);
    }
 
    //recursively remove adj duplicates in remaining string
    char* rem_str = recRemoveAdjDup(s+1, last_removed);
 
    //a) If first character of rem_str matches with the first character of original string, 
    //remove the first character from rem_str.
    if (rem_str[0] && rem_str[0] == s[0])
    {
        *last_removed = s[0];
        return (rem_str+1); // Remove first character
    }
 
    //b) If remaining string becomes empty and last removed character
    // is same as first character of original string.
    if (rem_str[0] == '\0' && *last_removed == s[0])
         return rem_str;
 
    //c) If the two first characters of s and rem_str don't match, 
    // append first character of s before the first character of
    // rem_str. 
    rem_str--;
    rem_str[0] = s[0];
    return rem_str;
}
 
char *removeAdjDup(char *s)
{
    char last_removed = '\0';
    return recRemoveAdjDup(s, &last_removed);
}

int main()
{
    char s1[] = "abssbe";
    cout << removeAdjDup(s1) << endl;
 
    char s2[] = "adaaacad";
    cout << removeAdjDup(s2) << endl;
 
    return 0;
}

Yoxla

 

Şərh yaz

Translate »