Anagram / partial anagram检测算法发现错误答案

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

你的算法的问题是这一行不起作用：

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;
}

Answer 2

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