Напишите функцию, которая возвращает true, если 2 переданные ей строки таковы, что все символы первой строки уникально присутствуют во второй строке.

Question

Эффективный и O (n) код для этого в c ?? Я знаю, что решение O (n * n)

stringCompare(str1, str2){
int freq1[100] = {0}, i;
int freq2[100]  = {0};

for(i=0; i<=strlen(str1); i++){
     freq1[str1[i]]+ = 1;
}

for(i=0; i<=strlen(str2); i++)

{
     freq2[str2[i]]+ = 1;
 }

for(i=0;i<26;i++){
     if(freq1[i]!=freq2[i])
      return 0;
   return 1;

}

}

Answer 1

Я немного изменил псевдокод MAK, поэтому он использует только один массив частотных счетчиков. Положительное значение в окончательном массиве freq означает, что символ в s1 не в s2. Отрицательное значение указывает на дополнительные символы в s2.

function same(s1,s2):
    freq=array of zeros

    for i=0 to length of s1:
       freq[s1[i]]+=1

    for i=0 to length of s2:
       freq[s2[i]]-=1

    for i=0 to alphabet_size:
        if not freq[i]=0
            return "no"
    return "yes"

Answer 2

Подсчитайте частоту каждого символа в первой строке, а также частоту во второй строке.Если оба значения частоты одинаковы для всех символов, у нас есть совпадение.

Я бы опубликовал код, но это слишком похоже на домашнюю работу.Объяснения должно быть достаточно.

РЕДАКТИРОВАТЬ:

Псевдокод:

function same(s1,s2):
    freq1=array of zeros
    freq2=array of zeros

    for i=0 to length of s1:
       freq1[s1[i]]+=1

    for i=0 to length of s2:
       freq2[s2[i]]+=1

    for i=0 to alphabet_size:
        if not freq1[i]=freq2[i]:
            return "no"
    return "yes"

Answer 3

1. количество вхождений для всех символов во 2-й строке (поиск 1 строки)
2. для каждого символа в 1-й строке проверьте, равно ли его количество во 2-й строке 1 (поиск 1 строки)

Таким образом, вам нужно будет просмотреть каждую строку один раз + буфер памяти с размером диапазона возможных значений символов.

Этот подход будет проверять, появляется ли каждый символ из первой строки во второй точно один раз. Изменение его для проверки того, что каждый символ появляется в обеих строках одинаковое количество раз (если это проблема), должно быть тривиальным.

Answer 4

Не могу придумать решение O (n), но O (nlogn) очевидно: сортировка символов строк и сравнение результатов на равенство