檢查排列而不修改原始字符串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，以便可以將修改後的副本中的字符相加。在這種情況下，如果修改副本中所有字符的和等於比較字符串的整數長度，則字符串將是字母。