1

私はインターネットから引っ張ってきたこのコードを持っています。これが行うことは、2 つの文字列がアナグラムかどうかをチェックすることです。これは基本的に、同じ種類と量の文字で同じ量の文字を持っていることを意味します。たとえば、「scrap」と「craps」、「hear」と「hare」などです。など。とにかく、私の問題は、それがどのように機能するかを理解していないことです。誰かが私に少しの洞察を与えることができれば、それは役に立ちます! お時間をありがとうございました！それは有り難いです！具体的にはコードです。for ループの部分がわかりません。

boolean isAnagram(string s1, string s2) { 
    if (s1.length != s2.length) 
        return false; 
    char [] a1 = s1.toCharArray(); 
    char [] a2 = s2.toCharArray(); 
    for (int i = a1.length - 1; i >= 0; --i) { 
        int j; 
        for (j = a2.length - 1; j >= 0; --j) { 
            if (a1[i] == a2[j]) 
                break; 
            } 
            if (j < 0) 
                return false; 
    } 
    return true; 
}
4

2 に答える 2

3

このコードは、単純なことを行うのに大変な作業のように思えます。完全に理解して正しく動作するかどうかを検証するのは非常に困難です。

もっと単純なアプローチはどうですか？各文字列を文字ごとに並べ替えます。次に、文字列が互いにアナグラムである場合、それらの文字列は等しくなります。最適化として長さチェックを実行することはできますが、コードはそのチェックの有無にかかわらず正しい結果を返します。

私の Java はさびているので、JavaScript バージョンをあげさせてください。私はあなたがアイデアを取り、それを翻訳できると確信しています：

function isAnagram( s1, s2 ) {
    return(
        s1.length === s2.length  &&
        sortString(s1) === sortString(s2)
    );
}

function sortString( s ) {
    return s.split('').sort().join('');
}

function test( s1, s2, expected ) {
    var result = isAnagram( s1, s2 );
    var ok = ( result === expected ? 'OK' : '*FAIL*' );
    console.log( s1, s2, result, ok );
}

test( 'dog', 'cat', false );
test( 'bag', 'big', false );
test( 'bag', 'gab', true );
test( 'bags', 'gab', false );
test( 'foobar', 'baroof', true );
test( 'aaaa', 'abbb', false );

テストにより、次のログが得られます。

dog cat false OK
bag big false OK
bag gab true OK
bags gab false OK
foobar baroof true OK
aaaa abbb false OK

以下のコメントで、G. Bach は、他のアルゴリズムはこのアルゴリズムよりもかなり高速である可能性があるという優れた点を挙げています。2 つの特定の文字列がアナグラムであるかどうかを判断するタスクが説明どおりであれば、パフォーマンスはほとんど問題になりません。この単純なアルゴリズムでさえ、十分に高速なはずです。

OTOH、多数の文字列を処理して、どの文字列がどのアナグラムであるかを調べる場合、もちろんパフォーマンスがより重要になります。その場合でも、このようなシンプルでわかりやすい実装を「バッグの中」に置くことは価値があります。たとえば、この単純なアプローチをテスト ケースの一部として使用して、より高速なアルゴリズムを検証できます。

于 2013-03-23T08:44:47.073 に答える
0

外側のループで最初の文字列を1文字ずつ繰り返します。その文字が2番目の文字列に存在するかどうかを確認します。これは、内側のループで行われます。存在しない場合はfalseを返します。

それでおしまい。ただし、すべての条件を処理できるかどうかを確認する必要があります。

理想的には、コードを読み取るか、デバッガーを使用して1行ずつコードを実行することにより、このロジックを理解できるはずです。

于 2013-03-23T07:53:57.033 に答える