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 数据结构能够高效地存储和查找单词，适用于需要频繁输入和自动完成功能的场景。