Рубрики

Проверяйте палиндром после каждой замены персонажа

Дана строка str и Q запросов. Каждый запрос содержит пару целых чисел (i1, i2) и символ 'ch'. Нам нужно заменить символы в индексах i1 и i2 новым символом 'ch', а затем сказать, является ли строка str палиндромом или нет. (0 <= i1, i2 <длина_строки)

Примеры:

Input : str = "geeks"  Q = 2
        query 1: i1 = 3 ,i2 = 0, ch = 'e'
        query 2: i1 = 0 ,i2 = 2 , ch = 's'
Output : query 1: "NO"
         query 2: "YES"
Explanation :
        In query 1 : i1 = 3 , i2 = 0 ch = 'e'
                    After replacing char at index i1, i2
                    str[3] = 'e', str[0] = 'e'
                    string become "eeees" which is not
                    palindrome so output "NO"
        In query 2 : i1 = 0 i2 = 2  ch = 's'
                    After replacing char at index i1 , i2
                     str[0] = 's', str[2] = 's'
                    string become "seses" which is
                    palindrome so output "YES"

Input : str = "jasonamat"  Q = 3
        query 1: i1 = 3, i2 = 8 ch = 'j'
        query 2: i1 = 2, i2 = 6 ch = 'n'
        query 3: i1 = 3, i2 = 7 ch = 'a'
Output :
       query 1: "NO"
       query 2: "NO"
       query 3: "YES"

Простое решение заключается в том, что для каждого запроса мы заменяем символ в индексах (i1 и i2) новым символом 'ch', а затем проверяем, является ли строка палиндромом или нет.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска, становится ли строка палиндромом
// после каждого запроса.
#include<bits/stdc++.h>

using namespace std;

  
// Функция для проверки, является ли строка палиндромом или нет

bool IsPalindrome(string &str)

{

    int n = strlen(str);

    for (int i = 0; i < n/2 ; i++)

        if (str[i] != str[n-1-i])

            return false;

    return true;

}

  
// Принимает два входа для Q запросов. Для каждого запроса это
// печатает Да, если строка становится палиндромом, и Нет, если нет.

void Query(string &str, int Q)

{

    int i1, i2;

    char ch;

  

    // Обрабатываем все запросы по одному

    for (int q = 1 ; q <= Q ; q++ )

    {

        cin >> i1 >> i2 >> ch;

  

        // запрос 1: i1 = 3, i2 = 0, ch = 'e'

        // запрос 2: i1 = 0, i2 = 2, ch = 's'

        // заменить символ в индексах i1 и i2 новым 'ch'

        str[i1] = str[i2] = ch;

  

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

        (isPalindrome(str)== true) ? cout << "YES" << endl :

                                     cout << "NO" << endl;

    }

}

  
// Драйвер программы

int main()

{

    char str[] = "geeks";

    int Q = 2;

    Query(str, Q);

    return 0;

}

python3

# Python3 программа для поиска
# строка становится палиндромом
# после каждого запроса.

  
# Функция проверки строки
# это палиндром или нет

def isPalindrome(string: list) -> bool:

    n = len(string)

    for i in range(n // 2):

        if string[i] != string[n - 1 - i]:

            return False

    return True

  
# Принимает два входа для Q запросов.
# Для каждого запроса выводится Да
# если строка становится палиндромом
# и нет, если нет.

def Query(string: list, Q: int) -> None:

  

    # Обрабатывать все запросы по одному

    for i in range(Q):

  

        # Чтобы разделить пространство

        # ввод от пользователя

        inp = list(input().split())

  

        # парсинг пользовательских входных данных как целых

        # и строки / символ

        i1 = int(inp[0])

        i2 = int(inp[1])

        ch = inp[2]

  

        # запрос 1: i1 = 3, i2 = 0, ch = 'e'

        # запрос 2: i1 = 0, i2 = 2, ch = 's'

        # заменить символ в индексе

        # i1 & i2 с новым 'ch'

        string[i1] = string[i2] = ch

  

        # проверить строку палиндром или нет

        if isPalindrome(string):

            print("Yes")

        else:

            print("No")

  
Код водителя

if __name__ == "__main__":

    string = list("geeks")

    Q = 2

    Query(string, Q)

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

Входные данные :

3 0 e
0 2 s

Выход:

"NO"
"YES"

Временная сложность O (Q * n) (n — длина строки)

Эффективным решением является использование хеширования. Мы создаем пустой хэш-набор, в котором хранятся индексы, неравные по палиндрому ( Примечание : «мы должны хранить индексы только в первой половине строки, которая неравна»).

Given string "str" and length 'n'.
Create an empty set S and store unequal indexes in first half.
Do following for each query :
   1. First replace character at indexes i1 & i2 with 
      new char "ch"

   2. If i1 and/or i2 are/is greater than n/2 then convert 
      into first half index(es)

   3. In this step we make sure that S contains maintains 
      unequal indexes of first half.
      a) If str[i1] == str [n - 1 - i1] means i1 becomes 
         equal after replacement, remove it from S (if present)
         Else add i1 to S 
      b) Repeat step a) for i2 (replace i1 with i2)  

   4. If S is empty then string is palindrome else NOT

Ниже приведена реализация вышеуказанной идеи на C ++.

// Программа на C ++ / c проверяет, является ли данная строка палиндромной
// или нет после каждого запроса
#include<bits/stdc++.h>

using namespace std;

  
// Эта функция гарантирует, что множество S содержит
// неравные символы из первой половины. Это называется
// для каждого персонажа.

void addRemoveUnequal(string &str, int index, int n,

                              unordered_set<int> &S)

{

    // Если символ становится равным после запроса

    if (str[index] == str[n-1-index])

    {

        // Удалить текущий индекс из набора, если он

        // настоящее

        auto it = S.find(index);

        if (it != S.end())

            S.erase(it) ;

    }

  

    // Если не совпадает после запроса, вставить его в набор

    else

        S.insert(index);

}

  
// Принимает два входа для Q запросов. Для каждого запроса это
// печатает Да, если строка становится палиндромом, и Нет, если нет.

void Query(string &str, int Q)

{

    int n = str.length();

  

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

    // неравное положение в палиндроме

    unordered_set<int> S;

  

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

    // пройти только первую половину строки

    for (int i=0; i<n/2; i++)

        if (str[i] != str[n-1-i])

            S.insert(i);

  

    // прохождение запроса

    for (int q=1; q<=Q; q++)

    {

        // запрос 1: i1 = 3, i2 = 0, ch = 'e'

        // запрос 2: i1 = 0, i2 = 2, ch = 's'

        int i1, i2;

        char ch;

        cin >> i1 >> i2 >> ch;

  

        // Заменить символы в индексах i1 и i2 на

        // новый символ 'ch'

        str[i1] = str [i2] = ch;

  

        // Если i1 и / или i2 больше n / 2

        // затем конвертируем в первую половину индекса

        if (i1 > n/2)

            i1 = n- 1 -i1;

        if (i2 > n/2)

            i2 = n -1 - i2;

  

        // вызов функции addRemoveUnequal для вставки и удаления

        // неравные показатели

        addRemoveUnequal(str, i1 , n, S );

        addRemoveUnequal(str, i2 , n, S );

  

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

        S.empty()? cout << "YES\n" : cout << "NO\n";

    }

}

  
// Драйвер программы

int main()

{

    string str = "geeks";

    int Q = 2 ;

    Query(str, Q);

    return 0;

}

Входные данные:

3 0 e
0 2 s

Выход:

"NO"
"YES"

Сложность времени: O (Q + n) в предположении, что операции вставки, удаления и поиска занимают O (1) времени.

Эта статья предоставлена Nishant_Singh (Pintu) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Проверяйте палиндром после каждой замены персонажа

0.00 (0%) 0 votes