Skip to content

Instantly share code, notes, and snippets.

@leeelton
Last active February 11, 2019 01:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save leeelton/7427779a242ee7fc186d7ddbc14aa97c to your computer and use it in GitHub Desktop.
Save leeelton/7427779a242ee7fc186d7ddbc14aa97c to your computer and use it in GitHub Desktop.
ObjC Trie Insert and Find
// TrieNode
// TrieNodes hold a dictionary of child TrieNode objects keyed by their character.
// isValid == YES means that the word exists in the dictionary
@interface TrieNode : NSObject
@property (strong, nonatomic) NSMutableDictionary<NSString *, TrieNode *> *children;
@property (assign, nonatomic) BOOL isValid;
-(instancetype)init;
@end
@implementation TrieNode
+(instancetype)init {
self = [super init];
if (self) {
_children = [[NSMutableDictionary alloc] init];
_isValid = NO;
}
return self;
}
@end
- (void)insertWord:(NSString *)word intoTrie:(TrieNode *)trie {
NSUInteger len = word.length;
unichar buffer[len];
[word getCharacters:buffer range:NSMakeRange(0, len)];
TrieNode *current = trie;
for (int i = 0; i < len; ++i) {
BOOL trieContainsKey = [current.children objectForKey:@(buffer[i]).stringValue];
if (!trieContainsKey) {
TrieNode *newNode = [[TrieNode alloc] init];
[current.children setValue:newNode forKey:@(buffer[i]).stringValue];
current = newNode;
} else {
current = [current.children objectForKey:@(buffer[i]).stringValue];
}
}
current.isValid = YES;
}
- (BOOL)containsWord:(NSString *)word trie:(TrieNode *)trie {
NSUInteger len = word.length;
unichar buffer[len];
[word getCharacters:buffer range:NSMakeRange(0, len)];
TrieNode* current = trie;
for (int i = 0; i < len; ++i) {
TrieNode* nextNode = [current.children objectForKey:@(buffer[i]).stringValue];
current = nextNode;
}
return current.isValid;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment