0

可能重复：
有什么简单的方法可以判断单词列表是否是彼此的字谜？
查找两个单词是否是彼此的字谜

我编写了以下 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();
}

这工作正常并打印正确的 Not Anagrams 如果我如下交换两个字符串的名称，它会给出错误的答案

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

我知道 2 for 循环的编码方式，这很明显。

我能做些什么来改进这段代码并解决这个怪癖？

4

5 回答 5

6

仅考虑小写字母，您可以制作 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' 或者制作一个更大的向量，然后在你的代码中添加一些 if ......我会让你试试那个；）

于 2012-10-21T12:51:40.097 回答
3

基于 vmp 的解决方案，您可以使用一个 char 数组 [26] 来执行此操作。

  1. 遍历第一个字符串，将字母的数组元素加一。
  2. 遍历第二个字符串，将数组减一。
  3. 遍历字母数组并断言所有元素为零。

编辑：添加了一些代码（手头没有编译器，但概念应该没问题）

//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
}
于 2012-10-21T12:54:20.203 回答
3

@Goldenmean，这是另一个对两个字符串进行排序然后比较它们的解决方案。其他人讨论的字符计数会更有效，但这更有趣:-)

qsort是一个标准库排序函数，它将函数comp作为参数，并在重新排序列表时使用它来比较列表（在本例中为字符串）的元素。

#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;
}
于 2012-10-21T13:21:36.237 回答
2

您还没有编码重复字母的可能性。

取这两个字符串：

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 中。）

于 2012-10-21T12:51:02.973 回答
1

很抱歉，您的实施存在缺陷。这段代码：

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

只要求第二个字符串中的任何字符都存在于第一个字符串中。

因此，由于“mitt”的字母都在“mits”之内，并且长度相同，因此报告它们是字谜。反过来是不正确的。

即使您在另一个方向重复检查，这仍然行不通。

所以例如

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

更新：最好的解决方案是完全改变算法，根据 vmp 或（甚至更好）Mario the Spoon 的。

于 2012-10-21T12:54:29.203 回答