字谜/部分字谜检测算法找到不正确的答案 [英] Anagram / partial anagram detection algorithm finds incorrect answers

问题描述

我编写了以下方法来确定一个长词是否包含一个较短的词，并且我传递字母的顺序似乎会影响结果.

I've written the following method to find out whether a long word contains a shorter word, and the order in which I pass the letters appears to effect the outcome.

我注意到，如果我输入 absconds 和 bassy，它会正确报告 NO，但是如果我将字母按字母顺序排列并给它abcdnoss 和 abssy，它给出 YES.我不太确定这是为什么——有人能发现这个问题吗?

I've noticed that if I feed it absconds and bassy it correctly reports NO, but if I alphabetize the letters and give it abcdnoss and abssy, it gives YES. I'm not too sure why this is – can anyone spot the issue?

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

推荐答案

你的算法的问题是这条线不起作用:

The problem with your algorithm is that this line doesn't work:

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

如果你搜索的第一个字母在长词的末尾，那么长词就会变成一个空字符串，你就会跳出循环到YES.

If the first letter you search is at the end of the long word, then long word becomes an empty string, and you jump out of your loop to YES.

我会使用不同的算法，就像这样.我认为更容易看到正在发生的事情，因此更不容易出错:

I would use a different algorithm, like this. I think it's easier to see what's going on, and so less prone to errors:

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

这篇关于字谜/部分字谜检测算法找到不正确的答案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！