0

重複の可能性:
単語のリストが互いにアナグラムであるかどうかを簡単に見分ける方法は?
2 つの単語が互いにアナグラムであるかどうかを調べる

与えられた 2 つの文字列が互いのアナグラムであるかどうかを確認するために、以下の 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 を出力します。以下のように 2 つの文字列の名前を入れ替えると、間違った答えが返されます

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

2 つの for ループがコード化されている方法を知っていますが、これは明らかです。

このコードを改善し、この癖を解決するにはどうすればよいですか?

4

5 に答える 5

6

小文字のみを考慮すると、それぞれ長さが 26 の 2 つのベクトルを作成できます。

両方のすべての位置を 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

@Goldenmean、2 つの文字列を並べ替えてから比較する別のソリューションを次に示します。他の人が議論したように、文字カウントはより効率的になりますが、これはより興味深いです:-)

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 に答える
3

vmp のソリューションに基づいて、1 つの char 配列でこれを行うことができます[26]。

  1. 最初の文字列を反復処理し、文字の配列要素を 1 つ増やします。
  2. 2 番目の文字列を反復処理し、配列を 1 つ減らします。
  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 に答える
2

文字が繰り返される可能性をコーディングしていません。

次の 2 つの文字列を使用します。

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

最初の文字列の各文字について、コードは 2 番目の文字列の各文字をチェックして、どこかに同じ文字があるかどうかを確認します。それでは、最初の文字列を調べて、2 番目の最初の同一の文字を確認しましょう(これがコードの動作です)。

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]

ご覧のとおり、コードは 2 つの文字列がアナグラムであると見なします。最初の文字列の 2 文字が 2 番目の文字列の 1 文字だけに一致したためです。

解決策は、次の文字に進む前に、既に一致した文字を「切り取る」ことです。コーディングはお任せします！幸運を。

編集:そして、もちろん、私は忘れていました:コードが文字列 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;
    }

2 番目の文字列の任意の文字が最初の文字列に存在することだけが必要です。

したがって、「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;
    }
}

UPDATE : 最善の解決策は、アルゴリズムを完全に変更することです。vmp または (さらに良い) Mario the Spoon に従ってください。

于 2012-10-21T12:54:29.203 に答える