c# - 異なるアナグラムを分離する

Question

たとえば、特定の数の文字列がn配列にランダムな順序で格納されているとします。いくつかは、たとえばm1のアナグラムでstring1ありm2、 のアナグラムなどstring2です。特定の文字列のアナグラムである文字列を分離し、各セットの文字列の数を決定するための効率的なアルゴリズムは何でしょうか?

Answer 1

興味深い質問です。アナグラムについて私たちが知っていることは、2 つのことに要約されます。

• それらは同じ長さです。
• それらは同じ文字で構成されています。

最初の条件を決定するのは簡単ですが、2 番目の条件はそうではありません。最初に文字列の配列を長さでソートすることにより、2 番目のテストを実行する必要がある文字列の数を制限します。

2 番目のテストでは、string1.contains(string2[n]) をチェックするだけでなく、各文字列で同じ回数発生することも確認する必要があるようです。おそらく文字列の配列のコピーが必要ですが、文字列は不変であるため、それを char[] の配列にします。次に、コピー内の各文字列を構成文字で並べ替えることができます。アナグラムは string1 == string2 と一致するようになりました。

Answer 2

  #include<stdio.h>
#include<string.h>
int main()
{
  char a[100],b[100],c[100],d[100];
  char temp;
  int i,j;
  printf("Enter the first string\n");
         gets(a);
         printf("Enter the second string\n");
         gets(b);
  strcpy(d,a);
  strcpy(c,b);
  for(i=0;i<strlen(a);i++)
  {
  if(a[i]==' ')
  {
    temp=a[i];
    a[i]=a[i+1];
      a[i+1]=temp;
  }
  }
  a[strlen(a)]='\0';
  for(j=0;j<strlen(b);j++)
  {
    if(b[j]==' ')
    {
      temp=b[j];
      b[j]=b[j+1];
      b[j+1]=temp;
    }
}
  b[strlen(b)]='\0';
if(strlen(a)==strlen(b))
    for(i=0;i<strlen(a);)
    {
      for(j=i;j<strlen(b);j++)
      {
        if(a[i]==b[j])
        {
          temp=b[i];
        b[i]=a[i];
        b[j]=temp;
          i++;
          break;
        }
        }
      }
 if(strcmp(a,b)==0)
      printf("%s and %s are anagrams\n",d,c);
        else
      printf("%s and %s are not anagrams\n",d,c);
      return(0);
    }