How to build a trie data structure using Objective-C?

Question

Even if Objective-C is a superset of C, I would like some feedback on how to create a trie data structure using Objective-C. I started coding the interface, but I need help understanding how to add Trie nodes (like collection items) to store words.

@interface Trie : NSMutableArray {
   Trie *child;
   BOOL final;
}

@property(nonatomic, retain)Trie *child;
@property(nonatomic, assign)BOOL final;

-(void)addWord:(NSString *)_word;

@end

Answer 1

, , , . , . NSArrays, . . .

@interface Trie : NSObject

@property (nonatomic, strong) NSMutableArray *children;
@property (nonatomic, strong) NSString *key;
@property (nonatomic, readonly) BOOL isFinal;

- (void) addWord:(NSString *)word;
- (id) initWithKey:(NSString *)key;

@end

@implementation Trie

// designated initializer, initializes our array of children and sets the key
- (id) initWithKey:(NSString *)key
{
    if(self = [super init])
    {
        _key = key;
        _children = [NSMutableArray new];
    }
    return self;
}

- (void) addWord:(NSString *)word
{
    // no more characters left, this is our base case
    if(! word.length)
    {
       return;
    }

    Trie *childToUse;
    NSString *firstCharacter = [word substringToIndex:1];

    // look for an existing node to dive into
    for(Trie *child in _children)
    {
        if([child.key isEqualToString:firstCharacter])
        {
            childToUse = child;
            break;
        }
    }

    // create a new node if there isn't one
    if(! childToUse)
    {
        childToUse = [[Trie alloc] initWithKey:firstCharacter];
        [_children addObject:childToUse];
    }

    // we now have a node, add the rest of the word into our trie recursively
    [childToUse addWord:[word substringFromIndex:1]];
}

// no actual ivar is stored for this property, its value is returned dynamically by looking at the array count, which can change when more elements are added
- (BOOL) isFinal
{
    if(! _children.count)
    {
        return YES;
    }
    else
    {
        return NO;
    }
}

@end

root node, - [[Trie alloc] initWithKey:@""].

Answer 2

@Dima, , , , children Trie, children , , -.

Trie.h:

@interface Trie : NSObject

@property (nonatomic, strong, readonly) NSMutableArray <Trie *>*children;
@property (nonatomic, strong) NSString *key;

- (id)initWithKey:(NSString *)key;
- (void)addWord:(NSString *)word;
- (BOOL)isLeaf;

@end

Trie.m:

@interface Trie ()

@property (nonatomic, strong, readwrite) NSMutableArray <Trie *>*children;

@end

@implementation Trie

- (id)initWithKey:(NSString *)key
{
    if (self = [super init]) {
        _key = key;
    }

    return self;
}

- (void)addWord:(NSString *)word
{
    if (word.length == 0) {
        return;
    }

    if (!self.children) {
        self.children = [NSMutableArray new];
    }

    NSString *firstCharacter = [word substringToIndex:1];
    __block Trie *childToUse = nil;
    [self.children enumerateObjectsUsingBlock:^(Trie *child, NSUInteger idx, BOOL *stop) {
        if ([child.key isEqualToString:firstCharacter]) {
            childToUse = child;
            *stop = YES;
        }
    }];

    if (!childToUse) {
        childToUse = [[Trie alloc] initWithKey:firstCharacter];
        [self.children addObject:childToUse];
    }

    [childToUse addWord:[word substringFromIndex:1]];
}

- (BOOL)isLeaf
{
    return self.children.count == 0;
}

@end