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