objective-c - 逐个字符循环遍历两个字符串以查找部分字谜

Question

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

haystack 和 needle 按字母顺序重新排序(例如，tomatoes 将变为 aemoostt 和 toe 将变为 eot)。在某些情况下，这是可行的，但如果存在多个字母，就会出现问题。一个这样的错误示例是它认为 aaabrs 确实存在于 aabeirsz 中，显然它不应该存在，因为它包含三个 A。

如果有人可以浏览我的方法并找出问题所在，我将非常非常感激。提前致谢。

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

Answer 1

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

编辑 需要注意的是，我绝不是 Objective C 程序员，下面是关于如何为 haystack 构建频率表作为 NSCountedSet 的尝试:

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

对 needle 执行相同操作，然后遍历 needle 的计数并检查 haystack 的计数。