字符串字謎C程序

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 for循環編碼這種方式很明顯。

我該怎麼做才能改進這段代碼並解決這個問題？

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] 

正如你看到的，代碼認爲兩個字符串字謎，因爲它匹配第一個字符串中的兩個字母到第二個字母只有一個字母！

解決方法是在去下一個字母之前「剪掉」已經匹配的字母;我會把它留給你編碼！祝你好運。

編輯：而且，當然，我忘了：如果代碼成功地設法通過字符串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的解決方案，你可以用一個char數組[26]做到這一點。

1. 遍歷第一個字符串，將 字母的數組元素遞增1。
2. 迭代第二個字符串，將數組 減1。
3. 遍歷字母數組並聲明所有元素爲 爲零。

編輯：添加一些代碼（沒有編譯器在手，但概念應該是OK）

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

只要求所述第二串中任何的字符存在於第一串英寸

因此，由於「手套」的字母都在「mits」之內，並且長度相同，因此它會報告它們是anagrams。相反是不正確的。

即使您在其他方向重複檢查，這仍然不起作用。

因此，例如

mitttsson 

missstton 

將出現是字謎，因爲它們是相同的長度並且兩者都通過集合{M，I，T，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：最好的解決辦法就是完全改變了算法，按照VMP的或（甚至更好）馬里奧勺的。

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; 
}