Find string patterns (stored in an array) from another string with maximal match

Question

I have the following string:

"SIT SIT UP SIT UP AND EAT AND EAT CHARLIE PAPA SIT UP AND EAT FOUR JUMP IN THE AIR FOR WATER FIVE SECONDS"

I also have an array containing valid string structures. Here's an example

 NSArray *validphrases = @["SIT UP",
                            "SIT UP AND EAT",
                            "CHARLIE",
                            "PAPA",
                            "JUMP IN THE AIR FOR", 
                            "FOUR", 
                            "FIVE",
                            "SECONDS",
                            "JUMP IN THE WATER FOR" nil];

/** And the end result should be these valid phrases detected in order:
 1. Sit up
 2. Sit up and eat
 3. Charlie
 4. Papa
 5. Sit up and eat
 6. Four
 7. Jump in the air for
 8. Five
 9. Seconds */

If multiple strings match at a given point in the string, it should return the longest one, and then skip past it.

Whats the quickest way that I can find the validPhrases string patterns from the string provided omitting any other words that don't satisfy the validPhrase patterns

What this will do is filter the string taking all the extra words away leaving only validPhrases and put that in a new array called preCommands array My current implementation works like this, but there should be an easier way

1. Split string by components separated by the " " character.

2. Iterate through the components and find out if that current word:

   • Is present as a strings structure in the validPhrases array: If so then save that word into a preCOMMANDS array.
   • Else execute another array and continue checking the next word appending to the first word until the set of words matches a pattern from the validPhrases array
   • When it does match, add phrase to the preCOMMANDS array

This method of mine only works when the phrases are side by side each other in the string, For example

"SIT UP AND EAT" //will work but
"SIT SIT UP AND EAT" //will not work if you follow the formula

Is there an Objective-C method function that I can use to grab all phrases from a string in one go? I feel like I'm reinventing the wheel for something that I'm sure is possible with another method.

Answer 1

NSScanner will do the job for you. You need to move through the input string, finding matches as you go. You mentioned that the maximal match should always be made ("SIT UP AND EAT" takes precedence over "SIT UP"); that just means you need to try to match the longer string before the shorter.

The scanner manages its own position in the source string. Every time it makes a match, it moves to the end of it. When it doesn't match, however, it won't move; therefore if, at a certain position in the source, you can't match any target phrases, you have to move past that word manually. This is acomplished by scanning up to and then past the next bunch of delimiting characters -- in this case, just whitespace.

You may also want to take a look at ParseKit.

This NSScanner code passes the test from your question.

NSArray *validPhrases = @[@"SIT UP",
                          @"SIT UP AND EAT",
                          @"CHARLIE",
                          @"PAPA",
                          @"JUMP IN THE AIR FOR",
                          @"FOUR",
                          @"FIVE",
                          @"SECONDS",
                          @"JUMP IN THE WATER FOR"];

NSSortDescriptor * sD = [[NSSortDescriptor alloc] initWithKey:@"length"
                                                    ascending:NO];
// Order targets by length to get maximal match at any given position.
validPhrases = [validPhrases sortedArrayUsingDescriptors:@[sD]];


NSString * input = @"SIT SIT UP SIT UP AND EAT AND EAT CHARLIE PAPA SIT UP AND EAT FOUR JUMP IN THE AIR FOR WATER FIVE SECONDS";

NSScanner * scanner = [NSScanner scannerWithString:input];

NSMutableArray * foundPhrases = [NSMutableArray array];
NSCharacterSet * whitespace = [NSCharacterSet whitespaceAndNewlineCharacterSet];

while( ![scanner isAtEnd] ){

    NSString * foundPhrase = nil;
    BOOL madeMatch = NO;
    for( NSString * phrase in validPhrases ){

        if( [scanner scanString:phrase intoString:&foundPhrase] ){
            // Got a match; store it and go on to the next position
            [foundPhrases addObject:foundPhrase];
            madeMatch = YES;
            break;
        }
    }

    // No match; step past this word and try the list again
    if( !madeMatch ){
        [scanner scanUpToCharactersFromSet:whitespace intoString:NULL];
        [scanner scanCharactersFromSet:whitespace intoString:NULL];
    }
}

Answer 2

You can try:

NSArray *filteres = [self.string filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"SELF LIKE %@", givedString]];

also you can try to build different predicate, depends what you exactly need, for instance:

[NSPredicate predicateWithFormat:@"SELF CONTAINS[cd] %@", givedString]

check here for more predicate formats: https://developer.apple.com/library/mac/documentation/Cocoa/Conceptual/Predicates/Articles/pSyntax.html