1

Okay, so I'm trying to compare two strings, one eight letters long, one that could be anything from 3-8 letters long, to see if the shorter one could be made from letters in the longer one. Following some algorithms and tips I've got something which nearly works, but not in all cases.

The haystack and needle are fed in re-sorted into alphabetical order (for example, tomatoes would become aemoostt and toe would become eot). In some cases this works, but the issues arise if multiples of a letter exist. One such broken example is that it thinks aaabrs does exist inside aabeirsz, where obviously it should not since it has three A's in it.

If anyone can take a browse through my methods and spot where the issue is occurring, I'd be hugely, hugely grateful. Thanks in advance.

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

I'd suggest that you further transform your input. After sorting by letter, build a frequency table that turns each string into a (letter, frequency) map. Then go through the shorter string's map and, for each key, if the key does not exist in the larger string's map or if the frequency in the larger string's map is smaller, reject as an anagram. Otherwise, it passes.

EDIT With the caveat that I am by no means an Objective C programmer, here's a stab at how to build a frequency table as an NSCountedSet for 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]];
}

Do the same for needle and then its a matter of iterating through the counts for needle and checking against the counts for haystack.

于 2012-11-14T16:26:01.347 に答える
0

The problem is that the search for the character from needle always searches the entire haystack. newHaystack is created correctly as the new substring from haystack, but it is never actually used. So, for example, the search for each character a always searches the entire original value aabeirsz.

于 2012-11-14T16:42:28.047 に答える