0

我的应用程序从文本字段接收用户的输入，并生成可以从字母组成的所有可能的单词。

如果用户键入“BOX”，程序会生成一个可变数组，其中包含以下单词：“BO”、“BOB”、“BOO”、“OX”。

我只需要过滤掉包含用户输入中不存在的重复字母的单词。所以，我需要过滤掉“BOB”和“BOO”。

我想另一种解决方案是首先避免生成 BOB 和 BOO，但我也没有弄清楚。

谢谢！

4

3 回答 3

3

要从给定单词的字母生成所有可能的组合（每个字母只使用一次），您可以使用以下递归方法：

- (NSArray *)allWordsFrom:(NSString *)word
{
    NSMutableArray *a = [NSMutableArray array];
    [self addAllWordsFrom:word withPrefix:@"" toMutableArray:a];
    return a;
}

- (void)addAllWordsFrom:(NSString *)letters withPrefix:(NSString *)prefix toMutableArray:(NSMutableArray *)a
{
    [letters enumerateSubstringsInRange:NSMakeRange(0, [letters length])
                    options:NSStringEnumerationByComposedCharacterSequences
                 usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) {
                     // Add one letter to the prefix:
                     NSString *word = [prefix stringByAppendingString:substring];
                     [a addObject:word];
                     // Build combinations with remaining letters:
                     NSString *remainingLetters = [letters stringByReplacingCharactersInRange:substringRange withString:@""];
                     if ([remainingLetters length] > 0) {
                         [self addAllWordsFrom:remainingLetters withPrefix:word toMutableArray:a];
                     }
                 }];
}

对于单词“BOX”，这将创建列表

B、BO、BOX、BX、BXO、O、OB、OBX、OX、OXB、X、XB、XBO、XO、XOB

之后您不必过滤数组。

于 2013-04-30T12:06:49.553 回答
1

这是将根据要求过滤您的数组的代码。如果您愿意，可以稍微修改它以使用谓词过滤。

NSCountedSet *letterBinsForWord(NSString *word)
{
    NSCountedSet *bins = [NSCountedSet set];
    for (NSUInteger i=0, n=word.length;  i<n;  i++) {
        NSString *letter = [word substringWithRange:NSMakeRange(i, 1)];
        [bins addObject:letter];
    }
    return bins;
}

BOOL letterBinsIncludesBins(NSCountedSet *set0, NSCountedSet *set1)
{
    for (NSString *letter in set1) {
        if ([set0 countForObject:letter] < [set1 countForObject:letter])
            return NO;
    }
    return YES;
}


int main (int argc, const char * argv[])
{
    @autoreleasepool {

        NSString *userText = @"boox";
        NSArray  *words = @[@"box",@"ox",@"boo",@"booo",@"bo",@"bin"];

        NSCountedSet *letterBins = letterBinsForWord(userText);
        NSMutableArray *filteredWords = [NSMutableArray array];

        for (NSString *word in words) {
            NSCountedSet *bins = letterBinsForWord(word);
            if (letterBinsIncludesBins(letterBins, bins))
                [filteredWords addObject:word];
        }

        NSLog(@"Filtered words: %@",filteredWords);
    }
    return 0;
}

对于 userText “boox”（带有两个“o”），我得到以下输出：

Filtered words: (
    box,
    ox,
    boo,
    bo
于 2013-04-30T12:08:17.637 回答
1

假设您的数组包含所有可能的字母，allCombinations您可以使用 filteredArrayUsingPredicateNSArray 的功能来创建过滤数组。因此，您需要定义一个可以使用块轻松完成的预测：

NSPredicate *filterPrecicate = [NSPredicate predicateWithBlock: ^BOOL(id obj, NSDictionary *bind){
    BOOL filterEntry;
    // do actually filtering a set filterEntry to YES/NO
    return filterEntry
}];

创建块后，您可以进行过滤：

NSArray *filteredCombinations = [allCombinations filteredArrayUsingPredicate: filterPrecicate];
于 2013-04-30T12:03:20.013 回答