string - ocaml中反转字符串

Question

我有一个用于在 ocaml 中反转字符串的函数，但是它说我的类型错误。我不确定为什么或我能做什么:(

任何有关调试的提示也将不胜感激!

  28 let reverse s =
  29   let rec helper i =
  30     if i >= String.length s then "" else (helper (i+1))^(s.[i])
  31   in
  32     helper 0

错误:此表达式的类型为 char，但表达式应为类型 字符串

谢谢

Answer 1

您的实现不具有预期的(线性)时间和空间复杂度:它在时间和空间上都是二次的，因此它很难是所请求功能的正确实现。

字符串连接sa^sb分配一个大小为长度sa + 长度sb的新字符串，并用两个字符串填充它；这意味着它的时间和空间复杂度与长度之和呈线性关系。当每个字符迭代一次此操作时，您将获得二次复杂度的算法(分配的内存总大小和副本总数将为 1+2+3+....+n).

要正确实现此算法，您可以:

• 分配一个预期大小的字符串，并将其与输入字符串的内容相反的位置进行变异

• 创建一个由反向大小为 1 的字符串组成的字符串列表，然后使用 String.concat 一次性连接所有这些字符串(这会分配结果并仅复制字符串一次)

• 使用Buffer模块，旨在迭代累积字符或字符串而不表现出二次行为(它使用动态调整大小策略，添加字符摊销常数时间)

第一种方法是最简单也是最快的，但是在想要连接字符串的更复杂的应用程序中，其他两种方法会变得更有趣，但一步知道最终结果是什么并不那么简单。