Проверить перестановки без изменения исходной строки C

Question

Я делаю проверку, являются ли 2 строки перестановками. Я сортирую строки, затем сравниваю каждого персонажа друг с другом. Тем не менее, я думаю, что мой процесс сортировки также изменяет исходные строки (я очень плохо отношусь к указателям и передаю их по ссылке).

Есть ли способ проверить, не изменяя исходные строки?

Я также пробовал использовать strcpy, но я действительно не знаю, как его использовать. Я попробовал это в моей функции проверки():

char temp[128]; 
strcpy(temp, word); 

Ниже мой код. Я вызываю функцию areAnagram из другой функции, как это:

void check(char *word, struct Entry *en) { 
    if (areAnagram(en->word, word) == 1) { 
     //printf("EW:%s W:%s\n", en->word, word); 
     //For example, this should return something like 
     // EW:silent W:listen 
     //But I got 
     // EW:eilnst W:eilnst 
    } 
} 

Структура для въезда:

typedef struct Entry { 
    char *word; 
    int len; 
    struct Entry *next; 
} Entry; 

Вот процесс проверки анаграмма:

void quickSort(char *arr, int si, int ei); 

int areAnagram(char *str1, char *str2) 
{ 
    // Get lenghts of both strings 
    int n1 = strlen(str1); 
    int n2 = strlen(str2); 

    // If lenght of both strings is not same, then they cannot be anagram 

    if (n1 != n2) { 
     return 0; 
    } 

    // Sort both strings 
    quickSort (str1, 0, n1 - 1); 
    quickSort (str2, 0, n2 - 1); 

    int i; 
    // Compare sorted strings 
    for (i = 0; i < n1; i++) { 
     if (str1[i] != str2[i]) { 
     return 0; 
     } 
    } 

    return 1; 
} 

void exchange(char *a, char *b) 
{ 
    char temp; 
    temp = *a; 
    *a = *b; 
    *b = temp; 
} 

int partition(char A[], int si, int ei) 
{ 
    char x = A[ei]; 
    int i = (si - 1); 
    int j; 

    for (j = si; j <= ei - 1; j++) { 
     if(A[j] <= x) { 
     i++; 
     exchange(&A[i], &A[j]); 
     } 
    } 

    exchange (&A[i + 1], &A[ei]); 
    return (i + 1); 
} 

void quickSort(char A[], int si, int ei) 
{ 
    int pi; /* Partitioning index */ 
    if(si < ei) { 
     pi = partition(A, si, ei); 
     quickSort(A, si, pi - 1); 
     quickSort(A, pi + 1, ei); 
    } 
} 

Answer 1

Существует лучший способ проверки являются ли две строки анаграммами. Вы можете создать массив для хранения счета каждого символа в первой строке (прирастить индекс значения ASCII в массиве). Затем пройдите вторую строку и уменьшите счет каждого символа (индекс значения ASCII в массиве). Теперь проверьте, все ли элементы массива равны нулю, если да, то это анаграммы в противном случае.

int arr [123]; предположим, что две строки: s1 = "abba" и s2 = "baba"

при обходе первой строки arr [97] = 2, arr [98] = 2;

при перемещении второго массива arr [97] = 0, arr [98] = 0;

Теперь, если вы пройдете весь массив, тогда все элементы будут равны нулю.

Но если две строки s1 = "ABBA" и s2 = "ДКС"

при пересечении первой строки обр [97] = 2, обр [98] = 2;

при перемещении второй строки arr [97] = 0, arr [98] = 1, arr [99] = - 1;

Поскольку все элементы массива не равны нулю, они не являются анаграммами.

Сложность алгоритма выше O (n).

Надеюсь, это поможет.

Answer 2

сделать копию с помощью STRCPY:

char *copy = malloc(strlen(word) + 1); // can use a temporary buffer, but this  allows variable length inputs 
strcpy(copy, word); 
// use copy as your temporary string 

free(copy); 

Answer 3

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

/* OPTION 1: let the compiler build your table */ 
static const int A=0x0000001; 
static const int B=0x0000002; 
static const int C=0x0000004; 
/* continue to double for other letters until ... */ 
static const int Z=0x4000000; 

/* OPTION 2: calculate a cheap hash for each letter */ 
/* Returns 0 for anagram similar to strcmp */ 
int anagram (const char* word1, const char* word2) 
{ 
    /* strings must be equal length */ 
    if (strlen(word1) != strlen(word2)) 
     return -1; 

    unsigned long sum1 = 0; 
    unsigned long sum2 = 0; 
    char c; 
    for (int i = 0 ; word1[i] != '\0' ; i++) 
    { 
     /* use toupper() function here if case insensitive */ 
     c = toupper(word1[i]); 
     sum1 += 1 << (c - 'A'); 
    } 
    for (int i = 0 ; word2[i] != '\0' ; i++) 
    { 
     /* use toupper() function here if case insensitive */ 
     c = toupper(word2[i]); 
     sum2 += 1 << (c - 'A'); 
    } 
    return (int)(sum1 - sum2); /* ignore overflow */ 
} 

Функция анаграммы выше не проверена и написана для ясности. Вам нужно будет включить ctype.h для преобразования футляра с помощью toupper().

Наконец, вы можете сделать копию одной из строк, пересечь другую строку, вызывающую strchr() на каждом символе, чтобы найти соответствующий символ в копии. Если strchr() возвращает NULL, тогда нет анаграммы, в противном случае, если strchr() возвращает действительный указатель, используйте его для изменения копии, например. установите для значения char значение 0x01, чтобы вы могли суммировать символы в модифицированной копии. В этом случае строки были бы анаграммами, если сумма всех символов в модифицированной копии равна целочисленной длине строки сравнения.