algorithm - 插入缩写词

Question

问题:将单词翻译成首字母缩写词，其中单词的首字母缩写词:

1. 至少有一个字符的前缀。
2. 至少有一个字符的后缀。
3. 中间剩余的字符被替换为一个数字，该数字表示替换了多少个中间字符。
4. 如果单词的长度>2，则替换的中间字符数必须>0。
5. 每个首字母缩略词都唯一地映射到一个词。例如，如果 "abide"=> "a3e"，那么随后，"aside"也不能翻译为 "a3e"。它可以是 as2e 或 a2de。

一些例子:

localization => l10n 

或

localization => loc8n 

或

localization => l8ion

解决这个问题的好方法是什么？哪种数据结构最适合？例如:HashSet? 树？

Answer 1

我会做一些观察，尽管我没有一个非常明显的好主意来解决问题。与 CS 文献中的往常一样，我将使用“字符串”表示字母序列，使用“语言”表示一组字符串。

• 我们不妨只考虑字符串长度固定的字母表。毕竟，“localization”的缩写不可能等同于“lotion”的任何缩写。
• 当然有可能没有解决方案。语言 {acb, adb, aeb} 不能按照您的规则正确缩写——甚至语言 {ab} 也不能。这并不会真正影响算法本身，但在您编写代码和测试时值得牢记这一点。

• 给定一种语言，我们可以按照以下过程描述该语言的任何缩写:

  1. 如果语言是空的:停止，我们完成了，我们成功了!
  2. 如果语言包含长度为 2 或更短的字符串:停止，我们完成了，我们失败了。
  3. 将语言划分为子语言，这些子语言的字符串都以相同的字母开头，并且都以相同的字母结尾。例如，{ready, robby, roady, legal, loyal, regal, royal} 将被划分为三种语言 {ready, robby, roady}(所有字符串均以“r”开头并以“y”结尾)， {legal, loyal}(所有字符串以“l”开头并以“l”结尾)和{regal, royal}(所有字符串以“r”开头并以“l”结尾)。
  4. 对于每种子语言(例如，{ready, robby, roady}):
     1. 选择要完全缩写的字符串；例如，我们可能会选择“准备就绪”。然后发出缩写及其映射；在本例中为“r3y”和“准备就绪”。
     2. 选择语言的右导数(分别为左导数)减去我们为其发出缩写的字符串，然后从第 1 步重新开始。将最后一个(分别为第一个)字母添加到由递归步骤。例如，如果我们在这里选择左导数，我们将在语言 {obby, oady} 上递归生成的所有缩写词的开头添加“r”。

  您可能有点担心第 4-1 步不太正确；也许有时需要在递归步骤中进行所有 缩写。但很容易看出事实并非如此:如果我们必须这样做，我们当然可以通过选择任何一个递归缩写并将其提升为来“改进”缩写(在增加省略字母总数的意义上)在没有引起任何冲突的情况下由步骤 4-1 提出。

  这立即提出了一种可以遍历所有有效缩写的搜索算法。我把它留给你，你是想通过某种度量找到“最佳”缩写，还是只想找到一个。在后一种情况下，您在第 4 步中尝试选择的顺序可能会显着影响您找到的第一个缩写的质量，尽管在我的脑海中我没有看到任何有原则的选择方式——只有启发式。

• 最小 DFA 支持所有必要的操作(空性测试、分区、代表性选择或枚举以及右导数和左导数)，具有公平的时间效率，并且非常节省空间。