Last active
February 11, 2019 01:12
-
-
Save leeelton/7427779a242ee7fc186d7ddbc14aa97c to your computer and use it in GitHub Desktop.
ObjC Trie Insert and Find
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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