Строка анаграммы ПРОГРАММА С

Question

Можно создать дубликат:
What is an easy way to tell if a list of words are anagrams of each other?
finding if two words are anagrams of each other

У меня есть ниже C код, написанный для проверки, если две заданные строки анаграммы друг друга. Я знаю, что это худшее с точки зрения сложности/эффективности, и есть намного лучшие способы сделать это.

#include "stdio.h" 

main() 
{ 
char s1[]="mist"; 
char s2[]="mitt"; 
int i,j,isanag=0; 

if(strlen(s1)!=strlen(s2)) 
    printf("Not anagrams\n"); 

for(i=0;i<strlen(s1);i++) 
{ 
    isanag=0; 
    for(j=0;j<strlen(s2);j++) 
    { 
     if(s1[i]==s2[j]) 
     { 
      isanag = 1; 
      break; 
     } 
    } 
    if(isanag == 0) 
    { 
     printf("Not anagrams\n"); 
     getch(); 
     exit(0); 
    } 

} 

printf("Yes Anagrams\n"); 
getch(); 
} 

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

char s1[]="mitt"; 
char s2[]="mist"; 

Я знаю способ, 2 для петель кодируются это очевидно.

Что я могу сделать для улучшения этого кода и устранения этой причуды?

Answer 1

Вы не указали на возможность повторных букв.

Возьмите эти две строки:

char s1[]="mitt"; 
char s2[]="mist"; 

Для каждой буквы в первой строке, ваш код проверяет каждую букву второй строки, чтобы увидеть, если есть идентичное письмо, в любом месте. Так давайте пройдем первую строку и проверьте первого идентичного письма в секунду (это то, что делает ваш код):

s1[0] ('m'): yes, at s2[0] 
s1[1] ('i'): yes, at s2[1] 
s1[2] ('t'): yes, at s2[3] 
s1[3] ('t'): yes, at s2[3] 

Как вы можете видеть, код считает, что две строки анаграммы, потому что он совпадал с двумя буквами в первой строке до только одна буква во втором!

Решение состоит в том, чтобы «вырезать» буквы, которые вы уже сопоставили, прежде чем перейти к следующей букве; Я оставлю это вам, чтобы закодировать! Удачи.

EDIT: И, конечно же, я забыл: если код успешно проходит весь путь через строку 1, вырезая буквы из строки 2, и в строке 2 есть буквы, что означает, что они не анаграммы! (В приведенном выше примере «s» будет оставлен в строке 2.)

Answer 2

Учитывая только строчную букву, вы можете сделать 2 вектора длины 26 каждый.

набор всех позиций до 0 в обоих из них, сделайте петлю в первой строке (s1) и приращение позиции в векторе:

int v1[26], v2[26], i; 
    for(i = 0; i < 26; i++) 
     v1[i] = v2[i] = 0; 
    for(i = 0; i < strlen(s1); i++) 
     v1[s1[i] - 'a']++; // 'a' would be on position 0, 'b' on position 1 and so on 
    for(i = 0; i < strlen(s2); i++) 
     v2[s2[i] - 'a']++; 

После этого вы просто цикл в векторах и посмотреть, если количество букв отличается

for(i = 0; i < 26; i++) 
     if(v1[i] != v2[i]) 
     { 
      printf("Not anagrams"); 
      exit(0); 
     } 
    printf("Anagrams"); 

, но если вы используете заглавные буквы вы можете сделать 4 векторов, и для нового вычитания с помощью «A» или сделать больший вектор и положить некоторые, если в вашем коде, ... Я позволю вам попробовать этот;)

Answer 3

На основе решения vmp вы можете сделать это с помощью одного массива символов [26].

1. Итерация над первой строкой, приращение элемента массива для письмо по одному.
2. Итерация по второй строке, уменьшение массива на единицу.
3. Итерации над матрицей алфавита и утверждение всех элементов ноль.

Edit: Добавлен код (без компилятора под рукой, но концепция должна быть в порядке)

//lower case only 
int isAnagram(char* left, char* right) 
{ 
    char theAlphabet[26]; 

    memset(theAlphabet, 0, sizeof theAlphabet); 


    int length = strlen(left); 

    for(int i=0; ++i; i < length) 
    { 
     if (0 == right[i]) 
     { //mismatching length 
     return 0; 
     } 

    ++theAlphabet[ left[i] - 'a' ]; 
    --theAlphabet[ right[ i ] - 'a' ]; 

    } 

    if (left[length] != 0 
     || right[length] != 0) 
    { 
    return 0; 
    } 


    for(int j=0; ++j; j < 26) 
    { 
     if (0 != theAlphabet[j]) 
     { 
     return 0; 
     } 
    } 

    return 1; //yes it is an anagram 
} 

Answer 4

Я извиняюсь, но ваша реализация несовершенна. Этот код:

for(j=0;j<strlen(s2);j++) 
{ 
    if(s1[i]==s2[j]) 
    { 
     isanag = 1; 
     break; 
    } 

только требует, чтобы любой символ во второй строке присутствует в первой строке.

Так как буквы «mitt» находятся внутри «mits», а длина одинакова, они сообщают, что они являются анаграммами. Обратное неверно.

Даже если вы повторили чек в другом направлении, это все равно не сработает.

Так, например

mitttsson 

missstton 

бы появляются быть анаграммы, так как они имеют одинаковую длину и оба генерируются множества {т, я, т, S, O, N}.

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

Это (неэффективно, поскольку он вычисляет неоднократно повторяемый письма) изменение:

for (i = 0; i < strlen(s1); i++) 
{ 
    int c = 0; 
    // How many times does character s1[i] occur in s1? 
    for (j = 0; j < strlen(s1); j++) 
    { 
     if (s1[i] = s1[j]) 
     { 
      // Improvement: if j < i, it means we already checked this letter. 
      // so we might break here... 
      c++; 
     } 
    } 
    // improvement: if c is 0 here, it means we can 'continue' for this letter 
    // has been already checked before. 

    // Subtract how many times it occurs in s2. 
    for (j = 0; j < strlen(s2); j++) 
    { 
     if (s1[i] = s2[j]) 
      c--; 
    } 
    // If occurrences are the same we expect difference to be 0. 
    if (c) 
    { 
     printf("Not anagrams\n"); 
     break; 
    } 
} 

UPDATE: лучшим решением является изменение алгоритма в целом, согласно ВМП или (что еще лучше) Марио в Ложка-х.

Answer 5

@ Goldenmean, вот еще одно решение, которое сортирует две строки, а затем сравнивает их. Счет символов, как обсуждались другие, будет более эффективным, но это более интересно :-)

qsort - это функция сортировки по стандартной библиотеке, которая принимает функцию comp как параметр и использует ее для сравнения элементов списка (a строка в этом случае), поскольку он повторно упорядочивает список.

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

static int comp(const void *a, const void *b) 
{ 
    const char *pa = a; 
    const char *pb = b; 

    return 
     (*pa > *pb) ? 1 : 
     (*pa < *pb) ? -1 : 
     0; 
} 

int main(int argc, char ** argv) 
{ 
    char s1[]="mits"; 
    char s2[]="mist"; 

    qsort(s1, strlen(s1), 1, comp); 
    qsort(s2, strlen(s2), 1, comp); 

    printf("%s : %s - %s\n", s1, s2, strcmp(s1, s2) ? "No" : "Yes"); 
    return 0; 
}