Remove only first instance of a character from a list of characters

Question

Hi All,

Here's what I want to do. I have 2 strings and I want to determine if one string is a permutation of another. I was thinking to simply remove the characters from string A from string B to determine if any characters are left. If no, then it passes.

However, I need to make sure that only 1 instance of each letter is removed (not all occurrences) unless there are multiple letters in the word.

An example:

String A: cant

String B: connect

Result: -o-nec-

Experimenting with NSString and NSScanner has yielded no results so far.

Answer 1

Hmmm, let's have a go:

NSString *stringA = @"cant";
NSString *stringB = @"connect";

NSUInteger length = [stringB length];
NSMutableCharacterSet *charsToRemove = [NSMutableCharacterSet characterSetWithCharactersInString:stringA];

unichar *buffer = calloc(length, sizeof(unichar));
[stringB getCharacters:buffer range:NSMakeRange(0, length)];

for (NSUInteger i = 0; i < length; i++)
{
    if ([charsToRemove characterIsMember:buffer[i]])
    {
        [charsToRemove removeCharactersInRange:NSMakeRange(buffer[i], 1)];
        buffer[i] = '-';
    }
}

NSString *result = [NSString stringWithCharacters:buffer length:length];

free (buffer);

Answer 2

An inefficient yet simple way might be something like this (this is implemented as a category on NSString, but it could just as easily be a method or function taking two strings):

@implementation NSString(permutation)
- (BOOL)isPermutation:(NSString*)other
{
    if( [self length] != [other length] ) return NO;
    if( [self isEqualToString:other] )    return YES;
    NSUInteger length = [self length];
    NSCountedSet* set1 = [[[NSCountedSet alloc] initWithCapacity:length] autorelease];
    NSCountedSet* set2 = [[[NSCountedSet alloc] initWithCapacity:length] autorelease];
    for( int i = 0; i < length; i++ ) {
        NSRange range = NSMakeRange(i, 1);
        [set1 addObject:[self substringWithRange:range]];
        [set2 addObject:[self substringWithRange:range]];
    }
    return [set1 isEqualTo:set2];
}
@end

Answer 3

This returns what your example asks for...

NSString* a = @"cant";
    NSString* b = @"connect";

    NSMutableString* mb = [NSMutableString stringWithString:b];
    NSUInteger i;
    for (i=0; i<[a length]; i++) {
        NSString* theLetter = [a substringWithRange:NSMakeRange(i, 1)];
        NSRange r = [mb rangeOfString:theLetter];
        if (r.location != NSNotFound) {
            [mb replaceCharactersInRange:r withString:@"-"];
        }
    }
    NSLog(@"mb: %@", mb);

However, I wouldn't call that a permutation. To me a permutation would only hold true if all the characters from string "a" were contained by string "b". In your example, since the letter a in cant isn't in string b then I would say that cant is not a permutation of connect. With this definition I would use this:

-(BOOL)isString:(NSString*)firstString aPermutationOfString:(NSString*)secondString {
    BOOL isPermutation = YES;
    NSMutableString* mb = [NSMutableString stringWithString:secondString];
    NSUInteger i;
    for (i=0; i<[firstString length]; i++) {
        NSString* theLetter = [firstString substringWithRange:NSMakeRange(i, 1)];
        NSRange r = [mb rangeOfString:theLetter];
        if (r.location != NSNotFound) {
            [mb deleteCharactersInRange:r];
        } else {
            return NO;
        }

    }
    return isPermutation;
}