检查排列而不修改原始字符串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”

while trarsing first string arr [97] = 2，arr [98] = 2;

while traversing second array arr [97] = 0，arr [98] = 0;

现在如果遍历整个数组，那么所有元素都将为零。

但是，如果两个字符串S1 = “ABBA” 和s2 = “ABAC”

在遍历第一串ARR [97] = 2，ARR [98] = 2;

while trarsing second string 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

你不想修改原始字符串你的标题状态，但解决方案使用快速排序，其中修改字符串。此外，排序 - 即使是快速优化的排序 - 也是一项昂贵的操作，对于您尝试解决的问题并不需要。您可以使用查找表来提高速度，并且不会修改原始字符串。您只需为每个字母创建一个唯一编号并对这些值进行求和。平等的金额将构成一个咒语。

/* 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 */ 
} 

上面的anagram函数未经测试，并且为了清晰起见而编写。您需要包含ctype.h才能使用toupper()转换案例。

最后，您可以制作其中一个字符串的副本，遍历每个字符上的另一个字符串strchr()以查找副本中的匹配字符。如果strchr()返回NULL，则不存在字谜，否则如果strchr()返回有效指针，则使用它来修改该副本，例如，将char值设置为0x01，以便可以将修改后的副本中的字符相加。在这种情况下，如果修改副本中所有字符的和等于比较字符串的整数长度，则字符串将是字母。