Рубрики

Удалить «b» и «ac» из заданной строки

Получив строку, исключите все «b» и «ac» в строке, вы должны заменить их на месте, и вам разрешается выполнять итерацию по строке только один раз. (Источник Google Интервью Вопрос )

Примеры:

acbac   ==>  ""
aaac    ==>  aa
ababac  ==>   aa
bbbbd   ==>   d

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Два условия:
1. Фильтрация всех 'b' и 'ac' должна выполняться за один проход
2. Не допускается дополнительное пространство.

Подход заключается в использовании двух индексных переменных i и j. Мы перемещаемся вперед в строке, используя 'i', и добавляем символы, используя индекс j, кроме 'b' и 'ac'. Хитрость здесь в том, как отследить «а» перед «с». Интересный подход заключается в использовании двух конечных автоматов. Состояние сохраняется до ДВУХ, когда предыдущий символ «а», в противном случае состояние ОДИН.
1) Если состояние равно ОДНО, то НЕ копируйте текущий символ для вывода, если выполняется одно из следующих условий
… А ) Текущий символ «b» (нам нужно удалить «b»)
Б) Текущий символ «а» (следующий символ может быть «с»)
2) Если состояние равно двум, а текущий символ не является «с», сначала нам нужно убедиться, что мы скопировали предыдущий символ «а». Затем мы проверяем текущий символ, если текущий символ не 'b' и не 'a', то мы копируем его в вывод.

C ++

// Программа на C ++ для удаления «b» и «ac» из входной строки
#include <iostream>

using namespace std;

#define ONE 1
#define TWO 2

  
// Основная функция, которая удаляет вхождения "a" и "bc"
// во входной строке

void stringFilter(char *str)

{

    // состояние изначально ОДИН (предыдущий символ не является)

    int state = ONE;

  

    // i и j - индексные переменные, i используется для чтения следующего

    // символ входной строки, j используется для индексов вывода

    // строка (измененная входная строка)

    int j = 0;

  

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

    for (int i = 0; str[i] != '\0'; i++)

    {

        / * Если состояние ЕДИНО, то НЕ копировать текущий символ

          вывести, если выполняется одно из следующих условий

           ... а) Текущий символ 'b' (нам нужно удалить 'b')

           ... б) Текущий символ «а» (следующий символ может быть «с») * /

        if (state == ONE && str[i] != 'a' && str[i] != 'b')

        {

            str[j] = str[i];

            j++;

        }

  

        // Если состояние ДВА, а текущий символ не 'c' (

        // мудро мы игнорируем как предыдущие, так и текущие символы)

        if (state == TWO && str[i] != 'c')

        {

            // Сначала копируем предыдущий 'a'

            str[j] = 'a';

            j++;

  

            // Затем копируем текущий символ, если он не 'a'

            // и 'b'

            if (str[i] != 'a' && str[i] != 'b')

            {

                str[j] = str[i];

                j++;

            }

        }

  

        // Изменить состояние в соответствии с текущим символом

        state = (str[i] == 'a')? TWO: ONE;

    }

  

    // Если последний символ был 'a', скопируйте его в вывод

    if (state == TWO)

    {

        str[j] = 'a';

        j++;

    }

  

    // Установить терминатор строки

    str[j] = '\0';

}

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

int main()

{

    char str1[] = "ad";

    stringFilter(str1);

    cout << str1 << endl;

  

    char str2[] = "acbac";

    stringFilter(str2);

    cout << str2 << endl;

  

    char str3[] = "aaac";

    stringFilter(str3);

    cout << str3 << endl;

  

    char str4[] = "react";

    stringFilter(str4);

    cout << str4 << endl;

  

    char str5[] = "aa";

    stringFilter(str5);

    cout << str5 << endl;

  

    char str6[] = "ababaac";

    stringFilter(str6);

    cout << str6 << endl;

  

    return 0;

}

питон

# Программа Python для удаления «b» и «ac» из входной строки

ONE = 1

TWO = 2

  
# Утилита для преобразования строки в список

def toList(string):

    l = []

    for x in string:

        l.append(x)

    return l

  
# Утилита для преобразования списка в строку

def toString(l):

    return ''.join(l)

  
# Основная функция, которая удаляет вхождения "a" и "bc"
# во входной строке

def stringFilter(string):

  

    # состояние изначально ОДИН (предыдущий символ не является)

    state = ONE

  

    # i и j - индексные переменные, i используется для чтения следующего

    # символ входной строки, j используется для индексов

    # строка вывода (измененная строка ввода)

    j = 0

  

    # Обрабатывать все символы входной строки один за другим

    for i in xrange(len(string)):

  

        # Если состояние ЕДИНО, то НЕ копировать текущий символ

        # для вывода, если выполняется одно из следующих условий

        # ... a) Текущий символ «b» (нам нужно удалить «b»)

        # ... б) Текущий символ «а» (следующий символ может быть «с»)

        if state == ONE and string[i] != 'a' and string[i] != 'b':

            string[j] = string[i]

            j += 1

  

        # Если состояние ДВА, а текущий символ не 'c' (

        # мудро мы игнорируем как предыдущие, так и текущие символы)

        if state == TWO and string[i] != 'c':

            # Сначала скопируйте предыдущий «а»

            string[j] = 'a'

            j += 1

  

            # Затем скопируйте текущий символ, если это не 'a' и 'b'

            if string[i] != 'a' and string[i] != 'b':

                string[j] = string[i]

                j += 1

  

        # Изменить состояние в соответствии с текущим персонажем

         state = TWO if string[i] == 'a' else ONE

  

    # Если последний символ был 'a', скопируйте его в вывод

    if state == TWO:

        string[j] = 'a'

        j += 1

  

    return toString(string[:j])

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

string1 = stringFilter(toList("ad"))

print string1

  

string2 = stringFilter(toList("acbac"))

print string2

  

string3 = stringFilter(toList("aaac"))

print string3

  

string4 = stringFilter(toList("react"))

print string4

  

string5 = stringFilter(toList("aa"))

print string5

  

string6 = stringFilter(toList("ababaac"))

print string6

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


Выход:

ad

aa
ret
aa
aaa

Расширение вышеприведенной проблемы, когда мы вообще не хотим, чтобы в выводе было «ac»:
Вышеприведенный код выглядит хорошо и, похоже, обрабатывает все случаи, но что, если входная строка имеет значение «aacacc», приведенный выше код выдает выходные данные как «ac», что выглядит правильно, так как удаляет последовательные вхождения «a» и «c». Что делать, если требуется, чтобы в выходной строке вообще не было «ac». Можем ли мы изменить вышеприведенную программу так, чтобы вывод выводился как пустая строка для ввода «aacacc», и выводился как «d», когда ввод «abcaaccd»? Оказывается, это также может быть сделано с учетом ограничений. Идея проста. Нам нужно добавить следующие строки внутрь для цикла вышеуказанной программы.

if (j>1 && str[j-2] == 'a' && str[j-1] =='c')

  j = j-2;

Смотрите это для различных тестовых случаев модифицированной программы.

Более простое решение исходной проблемы:

C ++

// // C ++ программа для удаления "b" и "ac" из входной строки
#include<bits/stdc++.h>

using namespace std;

  

void stringFilter(char *str)

{

    int n = strlen(str);

  

    int i = -1;  // предыдущий персонаж

    int j = 0;   // текущий персонаж

  

    while (j < n)

    {

        / * проверить, что текущий и следующий символ образует ac * /

        if (j < n-1 && str[j] == 'a' && str[j+1] == 'c')

            j += 2;

  

        / * если текущий символ b * /

        else if (str[j] == 'b')

            j++;

  

        / * если текущий символ 'c && последний символ в выводе

           это «а», поэтому удалите оба * /

        else if (i >= 0 && str[j] == 'c' && str[i] == 'a')

            i--,j++;

  

        / * иначе скопировать curr char в строку вывода * /

        else

            str[++i] = str[j++];

    }

    str[++i] = '\0';

}

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

int main()

{

    char str1[] = "ad";

    cout << "Input => " << str1 << "\nOutput => ";

    stringFilter(str1);

    cout << str1 << endl << endl;

  

    char str2[] = "acbac";

    cout << "Input => " << str2 << "\nOutput => ";

    stringFilter(str2);

    cout << str2 << endl << endl;

  

    char str3[] = "aaac";

    cout << "Input => " << str3 << "\nOutput => ";

    stringFilter(str3);

    cout << str3 << endl << endl;

  

    char str4[] = "react";

    cout << "Input => " << str4 << "\nOutput => ";

    stringFilter(str4);

    cout << str4 << endl << endl;

  

    char str5[] = "aa";

    cout << "Input => " << str5 << "\nOutput => ";

    stringFilter(str5);

    cout << str5 << endl << endl;

  

    char str6[] = "ababaac";

    cout << "Input => " << str6 << "\nOutput => ";

    stringFilter(str6);

    cout << str6 << endl << endl;

  

    char str[] = "abc";

    cout << "Input => " << str << "\nOutput => ";

    stringFilter(str);

    cout << str << endl << endl;

    return 0;

}

Джава

// Java-программа для удаления «b» и «ac» из входной строки

class GfG {

  
// Основная функция, которая удаляет вхождения "a" и "bc"
// во входной строке

static void stringFilter(char str[]) 

    int n = str.length; 

    

    int i = -1// предыдущий персонаж

    int j = 0;   // текущий персонаж

    

    while (j < n) 

    

        / * проверить, что текущий и следующий символ образует ac * /

        if (j < n-1 && str[j] == 'a' && str[j+1] == 'c'

            j += 2

    

        / * если текущий символ b * /

        else if (str[j] == 'b'

            j++; 

    

        / * если текущий символ 'c && последний символ в выводе

           это «а», поэтому удалите оба * /

        else if (i >= 0 && str[j] == 'c' && str[i] == 'a')  {

            i--;

            j++; 

        }

    

        / * иначе скопировать curr char в строку вывода * /

        else

            str[++i] = str[j++]; 

              

    

 System.out.println(new String(str).substring(0,i+1));

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

public static void main(String[] args) 

    String str1 = "ad"

    stringFilter(str1.toCharArray()); 

  

    String str2 = "acbac"

    stringFilter(str2.toCharArray());

  

    String str3 = "aaac"

    stringFilter(str3.toCharArray()); 

  

    String str4 = "react"

    stringFilter(str4.toCharArray()); 

  

    String str5 = "aa"

    stringFilter(str5.toCharArray()); 

  

    String str6 = "ababaac"

    stringFilter(str6.toCharArray()); 

}

питон

# Программа Python для удаления «b» и «ac» из входной строки

  
# Утилита для преобразования строки в список

def toList(string):

    l = []

    for x in string:

        l.append(x)

    return l

  
# Утилита для преобразования списка в строку

def toString(l):

    return ''.join(l)

  

def stringFilter(string):

  

    # длина строки

    n = len(string)

  

    i = -1

    j = 0

  

    while j < n:

  

        # Проверьте, является ли текущий и следующий символ образующимся

        if j < n-1 and string[j] == 'a' and string[j+1] == 'c':

            j += 2

  

        # Если текущий символ b

        elif string[j] == 'b':

            j += 1

  

        # если текущий символ 'c && последний символ в выводе

        # является 'a', поэтому удалите оба

        elif i >= 0 and string[j] == 'c' and string[i] == 'a':

            i -= 1

            j += 1

  

        # Иначе копировать curr char в строку вывода

        else:

            i += 1

            string[i] = string[j]

            j += 1

  

    i += 1

    return toString(string[:i])

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

string1 = "ad"

print "Input => " + string1 + "\nOutput => ",

print stringFilter(toList(string1)) + "\n"

  

string2 = "acbac"

print "Input => " + string2 + "\nOutput => ",

print stringFilter(toList(string2)) + "\n"

  

string3 = "aaac"

print "Input => " + string3 + "\nOutput => ",

print stringFilter(toList(string3)) + "\n"

  

string4 = "react"

print "Input => " + string4 + "\nOutput => ",

print stringFilter(toList(string4)) + "\n"

  

string5 = "aa"

print "Input => " + string5 + "\nOutput => ",

print stringFilter(toList(string5)) + "\n"

  

string6 = "ababaac"

print "Input => " + string6 + "\nOutput => ",

print stringFilter(toList(string6)) + "\n"

  

string7 = "abc"

print "Input => " + string7 + "\nOutput => ",

print stringFilter(toList(string7)) + "\n"

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

C #

// C # программа для удаления "b" и "ac" из входной строки

using System;

  

class GfG 

  

    // Основная функция, которая удаляет вхождения

    // "a" и "bc" во входной строке

    static void stringFilter(char []str) 

    

        int n = str.Length; 

        int i = -1; // предыдущий персонаж

        int j = 0; // текущий персонаж

        while (j < n) 

        

            / * проверить, что текущий и следующий символ образует ac * /

            if (j < n-1 && str[j] == 'a' && str[j+1] == 'c'

                j += 2; 

      

            / * если текущий символ b * /

            else if (str[j] == 'b'

                j++; 

      

            / * если текущий символ 'c && последний символ в выводе

            это «а», поэтому удалите оба * /

            else if (i >= 0 && str[j] == 'c' && str[i] == 'a'

            

                i--; 

                j++; 

            

      

            / * иначе скопировать curr char в строку вывода * /

            else

                str[++i] = str[j++]; 

              

        

        Console.WriteLine(new String(str)); 

    

  

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

    public static void Main() 

    {    

        String str1 = "ad"

        stringFilter(str1.ToCharArray()); 

          

        String str2 = "acbac"

        stringFilter(str2.ToCharArray()); 

          

        String str3 = "aaac"

        stringFilter(str3.ToCharArray()); 

          

        String str4 = "react"

        stringFilter(str4.ToCharArray()); 

          

        String str5 = "aa"

        stringFilter(str5.ToCharArray()); 

          

        String str6 = "ababaac"

        stringFilter(str6.ToCharArray()); 

    

  
// Этот код предоставлен
// PrinciRaj1992


Выход:

Input => ad
Output => ad

Input => acbac
Output =>

Input => aaac
Output => aa

Input => react
Output => ret

Input => aa
Output => aa

Input => ababaac
Output => aaa

Input => abc
Output =>

Спасибо Gaurav Ahirwar за то, что он предложил это более простое решение.

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

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

Удалить «b» и «ac» из заданной строки

0.00 (0%) 0 votes