gpt4 book ai didi

algorithm - 插入缩写词

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:17:53 26 4
gpt4 key购买 nike

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

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

一些例子:

localization => l10n 

localization => loc8n 

localization => l8ion

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

最佳答案

我会做一些观察,尽管我没有一个非常明显的好主意来解决问题。与 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 支持所有必要的操作(空性测试、分区、代表性选择或枚举以及右导数和左导数),具有公平的时间效率,并且非常节省空间。

关于algorithm - 插入缩写词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41452280/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com