Проверьте строки на наличие одинаковых символов в Objective-C - PullRequest
Новая
       39

Проверьте строки на наличие одинаковых символов в Objective-C

6 голосов
/ 02 января 2012

У меня есть массив строк, из которых я хотел бы извлечь только те, которые имеют уникальные наборы символов. (Например, «asdf» и «fdsa» будут считаться избыточными). Это метод, который я сейчас использую: 

NSMutableArray *uniqueCharSets = [[NSMutableArray alloc] init];
NSMutableArray *uniqueStrings = [[NSMutableArray alloc] init];        

for (NSString *_string in unique) {
    NSCharacterSet *_charSet = [NSCharacterSet characterSetWithCharactersInString:_string];
    if (![uniqueCharSets containsObject:_charSet]) {
        [uniqueStrings addobject:_string];
        [uniqueCharSets addObject:_charSet];
    }
}

Кажется, это работает, но это очень медленно и ресурсоемко. Кто-нибудь может придумать лучший способ сделать это?

Ответы [ 3 ]

1 голос
/ 02 января 2012
  1. Используя NSDictionary, сопоставьте лексикографически отсортированный эквивалент каждой строки с NSArray входных строк: (например, adfs => [afsd, asdf, ...])
  2. Пройдите по словарю,распечатка ключей (или их значений), которые имеют только одноэлементные значения массива
0 голосов
/ 02 января 2012

Единственное, что приходит мне в голову, это не использовать containsObject: поскольку NSMutableArray не упорядочен (в общем), мы можем предположить, что containsObject просто выполняет итерацию массива, начиная с самого начала, пока он не найдетобъект.Это означает O(n) (n сравнение в худшем случае).

Лучшее решение может состоять в том, чтобы упорядочить массив и использовать пользовательский метод поиска с использованием дихотомического подхода .Таким образом, у вас будет сложность O(log n).
Конечно, вы должны позаботиться о том, чтобы ваш массив упорядочивался (гораздо эффективнее, чем добавление и переупорядочение), поэтому вы должны использовать метод insertObject:atIndex:, чтобы правильно вставить элемент.

0 голосов
/ 02 января 2012

Я просто собрал краткий пример того, как я бы подошел к этому, но оказалось, что это более, странно, чем вы ожидаете.Во-первых, NSCharacterSet не реализует равенство для проверки содержимого.Используется только значение указателя.Исходя из этого, ваш пример не будет работать должным образом.

Мой подход заключается в использовании NSSet для решения этих задач за нас. 

@interface StringWrapper : NSObject
@property (nonatomic, copy) NSString *string;
@property (nonatomic, copy) NSData *charSetBitmap;
- (id)initWithString:(NSString*)aString;
@end

@implementation StringWrapper
@synthesize string, charSetBitmap;

- (id)initWithString:(NSString*)aString;
{
    if ((self = [super init]))
    {
        self.string = aString;
    }
    return self;
}

- (void)setString:(NSString *)aString;
{
    string = [aString copy];
    self.charSetBitmap = [[NSCharacterSet characterSetWithCharactersInString:aString] bitmapRepresentation];
}

- (BOOL)isEqual:(id)object;
{
    return [self.charSetBitmap isEqual:[object charSetBitmap]];
}

- (NSUInteger)hash;
{
    return [self.charSetBitmap hash];
}

@end

int main (int argc, const char * argv[])
{
    @autoreleasepool {
        NSMutableSet *stringWrappers = [[NSMutableSet alloc] init];
        NSArray *strings = [NSArray arrayWithObjects:@"abc",@"aaabcccc",@"awea",@"awer",@"abcde", @"ehra", @"QWEQ", @"werawe", nil];
        for (NSString *str in strings)
            [stringWrappers addObject:[[StringWrapper alloc] initWithString:str]];

        NSArray *uniqueStrings = [stringWrappers valueForKey:@"string"];
        NSLog(@"%@", uniqueStrings);

    }
    return 0;
}

Код довольно прост.Мы создаем объект-контейнер для кэширования результатов растрового представления набора символов.Мы используем растровое представление, потому что NSData соответственно реализует isEqual:.

...