0

2 つの文字列 (const char * で表される) がアナグラムかどうかを確認する最も効率的な方法は何ですか? 並べ替えて比較できることはわかっています。ただし、並べ替えは nlogn です。

助けてくれてありがとう。

編集: 試みを表示しないことに対して反対票を投じました。だから、私の試みは次のとおりです：

int anagram(const char * c1, const char *c2){
 char *s1=my_sort(c1);
 char *s2=my_sort(c2);
 return strcmp(s1,s2)==0?1:0;
}
4

1 に答える 1

5

それは私のブログ投稿の1つからのものです:)

/**
* Works for 0-127 ASCII string
**/
int isanagram(const char* s1,const char* s2){
    int hash[128];
    int i;
    for(i=0;i<128;i++)
        hash[i]=0;
    while(*s1) hash[*s1++]++;
    while(*s2) hash[*s2++]--;
    for(i=0;i<128;i++)
        if(hash[i]) return 0;
    return 1;
}

説明: アルファベットのすべての文字には、ハッシュ テーブル内の位置があります。s1 の各文字について、その文字のカウントをインクリメントし、s2 の各文字について、ハッシュ テーブル内の文字のカウントをデクリメントします。すべての文字の最後に 0 カウントがある場合、s1 と s2 の両方が同じ数の各文字を持ち、これがアナグラムの定義です。

複雑さ: n>128 の場合は O(n) 、n は s1 と s2 の長さの最大値

于 2013-04-25T00:56:17.480 に答える