Objective-C 实现字符串自动完成 using Trie（使用 Trie 数据结构）

使用 Trie 数据结构实现字符串自动完成是一个常见的算法问题。本文将展示一个完整的 Objective-C 示例代码，说明如何利用 Trie 实现字符串的自动完成功能。

Trie 节点定义

首先，我们需要定义一个 Trie 节点类，该类包含子节点和一个标志，用于指示该节点是否是一个单词的结束。

@interface TrieNode : NSObject  
  @property (nonatomic, strong) NSMutableDictionary *children;  
  @property (nonatomic, assign) Bool isEndOfWord;  
  @end

插入单词到 Trie 中

为了实现自动完成功能，我们需要将单词插入到 Trie 中。以下是 Objective-C 中的实现代码：

+ (void) insertWord:(NSString *)word intoTrie:(TrieNode *)root  
  {  
    TrieNode *currentNode = root;  
    for (char c in word) {  
      if (!currentNode.children[c]) {  
        currentNode.children[c] = [TrieNode new];  
      }  
      currentNode = currentNode.children[c];  
    }  
    currentNode.isEndOfWord = YES;  
  }

搜索 Trie 中的单词

在输入时，我们需要根据用户输入的字符逐步查找 Trie 中对应的节点。如果最终节点是单词的结束节点，则表示该单词存在于词典中。

+ (NSArray *) searchWord:(NSString *)input inTrie:(TrieNode *)root  
  {  
    TrieNode *currentNode = root;  
    NSMutableArray *results = [NSMutableArray new];  
    for (char c in input) {  
      if (!currentNode.children[c]) {  
        return results;  
      }  
      currentNode = currentNode.children[c];  
    }  
    if (currentNode.isEndOfWord) {  
      [results addObject:input];  
    }  
    return results;  
  }

完整示例代码

下面是一个完整的 Objective-C 实现示例，展示了 Trie 数据结构的使用方法：

@interface Trie  
  @property (nonatomic, strong) TrieNode *root;  
  - (void) insertWord:(NSString *)word;  
  - (NSArray *) searchWords:(NSString *)input;  
  @end  
 @interface TrieNode : NSObject 
@property (nonatomic, strong) NSMutableDictionary
    
      *children; 
@property (nonatomic, assign) Bool isEndOfWord; 
@end 
 @implementation Trie 
 
 
 (void) insertWord:(NSString *)word 
{ 
TrieNode *currentNode = [TrieNode new]; 
TrieNode *root = self.root; 
root.children = [NSMutableDictionary new]; 
for (char c in word) { 
if (!root.children[c]) { 
root.children[c] = [TrieNode new]; 
} 
root = root.children[c]; 
} 
root.isEndOfWord = YES; 
} 
 
 
 (NSArray *) searchWords:(NSString *)input 
{ 
TrieNode *currentNode = self.root; 
NSMutableArray *results = [NSMutableArray new]; 
for (char c in input) { 
if (!currentNode.children[c]) { 
return results; 
} 
currentNode = currentNode.children[c]; 
} 
if (currentNode.isEndOfWord) { 
[results addObject:input]; 
} 
return results; 
} 
@end
    

通过上述代码，我们可以轻松地在 Objective-C 中实现字符串的自动完成功能。Trie 数据结构能够高效地存储和查找单词，适用于需要频繁输入和自动完成功能的场景。