iphone - 在字符串中存储单词的优雅算法

Question

我有一个应用程序，用户可以在其中将文本输入自定义文本区域。如果用户点击文本区域，它会将光标移动到他们刚刚点击的点，从而使他们能够在文本区域的任何位置插入/删除文本。限制是文本区域的开头不能有空格，文本区域的任何一点都不能有连续的空格(也没有回车键来创建新行)。文本区域中的文本存储在名为“文本”的属性字符串中。

我需要开发的是一种高效的算法，可以跟踪文本区域中最宽的单词。当我说最宽时，我指的不是字符宽度，而是我通过将文本存储在 CTFrameRef 中并获取其大小来计算的实际像素宽度。

我已经想出了很多可以完成此任务的蛮力方法，但我想知道是否有人知道什么是时间和空间上最有效的方法来完成此任务？我显然需要某种数据结构来跟踪每个单词及其长度，我想过将所有单词存储在一个数组中并在插入或删除文本时更新它们，但想知道是否有人能想到更多最优？

Answer 1

你可以用 min-heap 来做到这一点，如果你能找到(或写)一个包含 modify-key 操作的。您将需要 increase-key 和 decrease-key 但好消息是两者都可以在 O(log N) 中实现。