Рубрики

Удалить символы из первой строки, которые присутствуют во второй строке

Напишите эффективную функцию C, которая принимает две строки в качестве аргументов и удаляет символы из первой строки, которые присутствуют во второй строке (строка маски).

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

Алгоритм: пусть первая входная строка будет «тестовой строкой», а строка, содержащая символы, которые нужно удалить из первой строки, будет «маской»
1: инициализировать:
res_ind = 0 / * индекс для отслеживания обработки каждого символа в строке i / p * /
ip_ind = 0 / * индекс для отслеживания обработки каждого символа в результирующей строке * /

2: Построить массив счетчиков из mask_str. Подсчет массива будет:
(Мы можем использовать здесь логический массив вместо массива int count, потому что нам не нужно считать, нам нужно знать только, присутствует ли символ в строке маски)
count ['a'] = 1
count ['k'] = 1
count ['m'] = 1
count ['s'] = 1

3: Обрабатывать каждый символ входной строки и, если счетчик этого символа равен 0, добавить только символ в результирующую строку.
str = «tet tringng» // «s» был удален, потому что «s» присутствовал в mask_str, но мы получили два дополнительных символа «ng»
ip_ind = 11
res_ind = 9

4: поставить '/ 0' в конце строки?

Реализации:

С

#include <stdio.h>
#include <stdlib.h>
#define NO_OF_CHARS 256

  
/ * Возвращает массив размером 256 счетчиков

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

int *getCharCountArray(char *str)

{

   int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);

   int i;

   for (i = 0; *(str+i);  i++)

      count[*(str+i)]++;

   return count;

}

  
/ * removeDirtyChars принимает в качестве аргументов две строки: First
строка (str) - это та, из которой функция удаляет грязные
персонажи. Вторая строка - это строка, содержащая все
грязные символы, которые необходимо удалить из первой строки * /

char *removeDirtyChars(char *str, char *mask_str)

{

  int *count  = getCharCountArray(mask_str);

  int ip_ind  = 0, res_ind = 0;

  while (*(str + ip_ind))

  {

    char temp = *(str + ip_ind);

    if (count[temp] == 0)

    {

        *(str + res_ind) = *(str + ip_ind);

        res_ind++;

    }

    ip_ind++;

  }    

  

  / * После указанного выше шага строка ngring.

    Удаление лишнего "iittg" после строки * /

  *(str+res_ind) = '\0';    

  

  return str;

}

  
/ * Драйверная программа для тестирования getCharCountArray * /

int main()

{

    char str[]         = "geeksforgeeks";

    char mask_str[]  = "mask";

    printf("%s", removeDirtyChars(str, mask_str));

    return 0;

}

Джава

// Java программа для удаления дубликатов, порядок
// символы не поддерживаются в этой программе

  

public class GFG 

{

    static final int NO_OF_CHARS = 256;

      

    / * Возвращает массив размером 256 счетчиков

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

    static int[] getCharCountArray(String str)

    {

       int count[] = new int[NO_OF_CHARS];

       for (int i = 0; i<str.length();  i++)

          count[str.charAt(i)]++;

         

       return count;

    }

      

    / * removeDirtyChars принимает в качестве аргументов две строки: First

    строка (str) - это та, из которой функция удаляет грязные

    персонажи. Вторая строка - это строка, содержащая все

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

    static String removeDirtyChars(String str, String mask_str)

    {

      int count[]  = getCharCountArray(mask_str);

      int ip_ind  = 0, res_ind = 0;

        

      char arr[] = str.toCharArray();

        

      while (ip_ind != arr.length)

      {

        char temp = arr[ip_ind];

        if(count[temp] == 0)

        {

            arr[res_ind] = arr[ip_ind];

            res_ind ++;

        }

            ip_ind++;

          

      }    

  

      str = new String(arr);

        

      / * После указанного выше шага строка ngring.

      Удаление лишнего "iittg" после строки * /

        

      return str.substring(0, res_ind);

        

    }

      

    // Метод драйвера

    public static void main(String[] args)

    {

        String str = "geeksforgeeks";

        String mask_str = "mask";

        System.out.println(removeDirtyChars(str, mask_str));

    }

}

питон

# Программа Python для удаления символов из первой строки, которая
# присутствуют во второй строке

NO_OF_CHARS = 256

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

def toList(string):

    temp = []

    for x in string:

        temp.append(x)

    return temp

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

def toString(List):

    return ''.join(List)

  
# Возвращает массив размером 256, содержащий количество символов
# в переданном массиве символов

def getCharCountArray(string):

    count = [0] * NO_OF_CHARS

    for i in string:

        count[ord(i)] += 1

    return count

  
# removeDirtyChars принимает в качестве аргументов две строки: First
# строка (строка) - это та, из которой функция удаляет грязные
# персонажи. Вторая строка - это строка, содержащая все
# грязные символы, которые необходимо удалить из первой строки

def removeDirtyChars(string, mask_string):

    count = getCharCountArray(mask_string)

    ip_ind = 0

    res_ind = 0

    temp = ''

    str_list = toList(string)

  

    while ip_ind != len(str_list):

        temp = str_list[ip_ind]

        if count[ord(temp)] == 0:

            str_list[res_ind] = str_list[ip_ind]

            res_ind += 1

        ip_ind+=1

  

    # После вышеприведенного шага строка ngring.

     # Удаление лишних "iittg" после строки

    return toString(str_list[0:res_ind])

  
# Функция драйвера для проверки вышеуказанных функций

mask_string = "mask"

string = "geeksforgeeks"

print removeDirtyChars(string, mask_string)

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

C #

// C # программа для удаления
// дубликаты, порядок
// символов нет
// поддерживается в этой программе

using System;

class GFG 

{

    static int NO_OF_CHARS = 256;

      

    / * Возвращает массив размера

    256 счетчиков

    символы в пройденном

    массив символов * /

    static int[] getCharCountArray(String str)

    {

        int[] count = new int[NO_OF_CHARS];

        for (int i = 0; i < str.Length; i++)

            count[str[i]]++;

              

        return count;

    }

      

    / * removeDirtyChars занимает два

    строка в качестве аргументов: первая

    строка (str) является одной из

    где функция удаляет грязный

    персонажи. Вторая строка

    строка, содержащая все

    грязные персонажи, которые нужны

    быть удаленным из первой строки * /

    static String removeDirtyChars(String str, 

                                   String mask_str)

    {

    int[] count = getCharCountArray(mask_str);

    int ip_ind = 0, res_ind = 0;

      

    char[] arr = str.ToCharArray();

      

    while (ip_ind != arr.Length)

    {

        char temp = arr[ip_ind];

        if(count[temp] == 0)

        {

            arr[res_ind] = arr[ip_ind];

            res_ind ++;

        }

        ip_ind++;

          

    

  

    str = new String(arr);

      

    / * После шага выше

    это нгринг. Удаление лишних

    «iittg» после строки * /

    return str.Substring(0, res_ind);

    }

      

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

    public static void Main()

    {

        String str = "geeksforgeeks";

        String mask_str = "mask";

        Console.WriteLine(removeDirtyChars(str, mask_str));

    }

}

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


Выход:

geeforgee

Сложность времени: O (m + n), где m — длина строки маски, а n — длина входной строки.

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

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

Удалить символы из первой строки, которые присутствуют во второй строке

0.00 (0%) 0 votes