1

好的，所以我正在尝试比较两个字符串，一个是八个字母长，一个可能是 3-8 个字母长，看看较短的字符串是否可以由较长的字母组成。遵循一些算法和技巧，我得到了一些几乎可以工作的东西，但并非在所有情况下都有效。

和被重新排序成字母顺序（例如，将成为haystack和将成为）。在某些情况下，这是可行的，但如果存在多个字母，则会出现问题。一个这样的坏例子是它认为内部确实存在，显然它不应该存在，因为它有三个 A。needletomatoesaemoostttoeeotaaabrsaabeirsz

如果有人可以浏览我的方法并发现问题发生的位置，我将非常非常感激。提前致谢。

- (void)viewDidLoad {
    [super viewDidLoad];
    BOOL doesWordExist = NO;
    doesWordExist = [self doesEightLetterWord: @"aabeirsz" containWord: @"aaabrs"];
    NSLog(doesWordExist ? @"Does it exist? Yes" : @"Does it exist? No");
}

- (BOOL) doesEightLetterWord: (NSString* )haystack containWord: (NSString *)needle {
    for (int i = 0; i < [needle length]; i++) {

        NSString *currentCharacter = [needle substringWithRange:NSMakeRange(i, 1)];
        NSCharacterSet *set = [NSCharacterSet characterSetWithCharactersInString: currentCharacter];
        NSLog(@"Current character is %@", currentCharacter);
        if ([haystack rangeOfCharacterFromSet:set].location == NSNotFound) {
            NSLog(@"The letter %@ isn't found in the word %@", currentCharacter, haystack);
            return NO;
        } else {
            NSLog(@"The letter %@ is found in the word %@", currentCharacter, haystack);
            int currentLocation = [haystack rangeOfCharacterFromSet: set].location;
            currentLocation++;
            NSString *newHaystack = [haystack substringFromIndex: currentLocation];
            NSString *newNeedle = [needle substringFromIndex: i + 1];
            NSLog(@"newHaystack is %@", newHaystack);
            NSLog(@"newNeedle is %@", newNeedle);

            if ([newNeedle isEqualToString:@""]) {
                return YES;
            }
        }
    }

return NO;
}
4

2 回答 2

2

我建议您进一步转换您的输入。按字母排序后，建立一个频率表，将每个字符串变成一个（字母，频率）图。然后遍历较短字符串的映射，对于每个键，如果较大字符串的映射中不存在该键，或者较大字符串的映射中的频率较小，则将其拒绝为字谜。否则，它会通过。

编辑需要注意的是，我绝不是 Objective C 程序员，这里是关于如何将频率表构建为NSCountedSetfor的尝试haystack：

NSCountedSet *haystackSet = [[NSCountedSet alloc] init];
NSUInteger len = [haystack length];
for (NSUInteger i = 0; i < len; i++) {
    unichar c = [haystack characterAtIndex:i];
    if ([[NSCharacterSet letterCharacterSet] characterIsMember:c])
        [haystackSet addObject:[NSNumber numberWithInteger:c]];
}

对 for 做同样needle的事情，然后它是遍历计数needle并检查计数的问题haystack。

于 2012-11-14T16:26:01.347 回答
0

问题是对字符的搜索needle总是搜索整个haystack. newHaystack被正确创建为 的新子字符串haystack，但从未实际使用过。因此，例如，对每个字符的搜索a总是搜索整个原始值aabeirsz。

于 2012-11-14T16:42:28.047 回答