Нахождение анаграммы - PullRequest
Новая
       11

Нахождение анаграммы

0 голосов
/ 03 марта 2019 
if (strlen(a) != strlen(b)) {
    printf("Not anagram");
} else {
    for (int i = 0; i < strlen(a); i++) {
        for (int j = 0; j < strlen(b); j++) {
            if (a[i] == b[j]) {
                len++;
            }
        }
    }
    if (len != strlen(a))
        printf("Not anagram");
    else
        printf("Anagram");
}
return 0;

Это фрагмент кода, чтобы проверить, являются ли 2 строки анаграммами.Как здесь можно обрабатывать повторяющиеся символы?Кроме того, можно ли сделать эту программу более оптимизированной?И какова будет сложность этого кода во время выполнения?

Ответы [ 3 ]

0 голосов
/ 03 марта 2019

Оптимальное решение, вероятно, будет основано на вычислении количества символов в каждой строке и последующем сравнении обоих значений.В идеале, мы должны использовать структуру данных Dictionary , но для простоты я продемонстрирую алгоритм на массиве: 

char *word1 = "word1";
char *word2 = "ordw1";

// C strings can have only 256 possible characters, therefore let's store counts in an array with 256 items.
int* letterCounts1 = calloc(256, sizeof(int));
int* letterCounts2 = calloc(256, sizeof(int));
size_t length1 = strlen(word1);
size_t length2 = strlen(word2);

for (size_t i = 0; i < length1; i++) {
    int letterIndex = word1[i] & 0xFF;
    letterCounts1[letterIndex] += 1;
}

for (size_t i = 0; i < length2; i++) {
    int letterIndex = word2[i] & 0xFF;
    letterCounts2[letterIndex] += 1;
}

bool isAnagram = true;

for (size_t i = 0; i < 256; i++) {
    if (letterCounts1[i] != letterCounts2[i]) {
        isAnagram = false;
        break;
    }
}

free(letterCounts1);
free(letterCounts2);

if (isAnagram) {
    printf("Anagram");
} else {
    printf("Not anagram");
}

Этот алгоритм имеет линейную (O(n)) сложность (итерация по«словарь» можно считать константой).

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

0 голосов
/ 03 марта 2019

Вот несколько ответов:

  • Ваш алгоритм не обрабатывает повторяющиеся буквы, он может возвращать ложные срабатывания.
  • Неясно, верно ли это в противном случае, потому что вы не опубликовали полное определение функции со всеми объявлениями и определениями, особенно, если len инициализирован в 0.
  • Имеет O (N 2 ) сложность времени или даже O (N 3 ) , если компилятор не можетоптимизировать многочисленные избыточные вызовы до strlen().

Вот простое решение для систем с 8-разрядными символами с линейной сложностью: 

#include <stdio.h>
#include <string.h>

int check_anagrams(const char *a, const char *b) {
    size_t counters[256];
    size_t len = strlen(a);
    size_t i;

    if (len != strlen(b)) {
        printf("Not anagrams\n");
        return 0;
    }
    for (i = 0; i < 256; i++) {
        counters[i] = 0;
    }
    for (i = 0; i < len; i++) {
        int c = (unsigned char)a[i];
        counters[c] += 1;
    }
    for (i = 0; i < len; i++) {
        int c = (unsigned char)b[i];
        if (counters[c] == 0) {
            printf("Not anagrams\n");
            return 0;
        }
        counters[c] -= 1;
    }
    printf("Anagrams\n");
    return 1;
}
0 голосов
/ 03 марта 2019

Прежде всего, это не правильное решение.Подумайте об этом в двух строках: «aabc» и «aade» a [0] == b [0], a [0] == b [1], a [1] == b [0] и a [1]== b [1].лен будет 4, но они не анаграмма.Сложность - это O (n ^ 2), равная n длине строки.

Поскольку @Sulthan ответил вам, лучшим подходом является сортировка строк, сложность которых равна O (n * log (n)) изатем сравните обе строки за один раз O (n).

Чтобы упорядочить строки в O (n * log (n)), вы не можете использовать пузырьковый метод, но вы можете использовать сортировку слиянием, как описано здесь: https://www.geeksforgeeks.org/merge-sort/

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

...