objective-c - アナグラム/部分アナグラム検出アルゴリズムが間違った答えを見つける

Question

長い単語に短い単語が含まれているかどうかを調べる次のメソッドを作成しました。文字を渡す順序が結果に影響するようです。

absconds餌を与えbassyて正しく報告NOすると、文字をアルファベット順に並べて と を与えるabcdnossとabssy、 が得られることに気付きましたYES。これがなぜなのかよくわかりません - 誰でも問題を見つけることができますか?

- (BOOL) does: (NSString* ) longWord contain: (NSString *) shortWord {
    while([longWord length] > 0 && [shortWord length] > 0) {
        NSCharacterSet *set = [NSCharacterSet characterSetWithCharactersInString: [shortWord substringToIndex: 1]];
        if ([longWord rangeOfCharacterFromSet: set].location == NSNotFound) {
            return NO;
        }
        longWord = [longWord substringFromIndex: [longWord rangeOfCharacterFromSet: set].location+1];
        shortWord = [shortWord substringFromIndex: 1];  
    }
    return YES;
}

Answer 1

 - (BOOL) does: (NSString* ) longWord contain: (NSString *) shortWord 
 {
      return ([longWord rangeOfString:shortWord].location != NSNotFound);   
 }

Answer 2

アルゴリズムの問​​題は、次の行が機能しないことです。

longWord = [longWord substringFromIndex: [longWord rangeOfCharacterFromSet: set].location+1];

検索する最初の文字が長い単語の末尾にある場合、長い単語は空の文字列になり、ループから YES にジャンプします。

このように、別のアルゴリズムを使用します。何が起こっているのかを簡単に確認できるため、エラーが発生しにくいと思います。

- (BOOL) does: (NSString* ) longWord contain: (NSString *) shortWord {
    NSMutableString *longer = [longWord mutableCopy];
    for (int i = 0; i<shortWord.length; i++) {
        NSString *letter = [shortWord substringWithRange:NSMakeRange(i, 1)];
        NSRange letterRange = [longer rangeOfString:letter];
        if (letterRange.location != NSNotFound) {
            [longer deleteCharactersInRange:letterRange];
        }else{
            return NO;
        }
    }
    return YES;
}