在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分配一个大小的新字符串length sa + length sb,并用两个字符串填充它; 这意味着它的时间和空间复杂度在长度之和上是线性的.当您对每个字符迭代此操作一次时,您将获得二次复杂度的算法(分配的内存总大小和总副本数1+2+3+....+n).

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

• 分配一个预期大小的字符串,并使用输入字符串的内容对其进行调整,反之

• 创建一个string list反向大小的字符串 - 一个字符串,然后用于String.concat连接所有这些字符串(分配结果并仅复制字符串一次)

• 使用缓冲模块,该模块用于迭代地累积字符或字符串而不显示二次行为(它使用动态调整大小策略,使得加上char摊销的常量时间)

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