在OCaml中反转字符串

Question

4

我有一个在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，但是应该是string类型

谢谢

- user2150929

3个回答

4

错误信息十分清晰明了。表达式s.[i]表示一个字符（字符串的第i个字符）。但是^运算符要求其参数为字符串。

要解决这个问题，您可以使用String.make 1 s.[i]。该表达式生成包含单个字符s.[i]的1个字符长的字符串。

在OCaml中递归处理字符串可能不太方便，因为没有一种很好的方法将字符串解构（将其分成几部分）。相应的反转列表代码看起来要漂亮得多。就这样 :-)

- Jeffrey Scofield

1

你也可以使用第三方库来实现。http://batteries.forge.ocamlcore.org/ 已经实现了一个反转字符串的函数。

- Alex

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gasche · Accepted Answer

你的实现没有达到预期的（线性）时间和空间复杂度：它在时间和空间上都是二次的，因此它几乎不是所请求特性的正确实现。

字符串连接sa^sb会分配一个大小为length sa + length sb的新字符串，并将其填充为两个字符串；这意味着它的时间和空间复杂度都是与长度总和成线性关系的。当您每个字符执行一次此操作时，您得到一个二次复杂度的算法（分配的内存总大小和副本总数将为1+2+3+....+n）。

要正确实现此算法，您可以选择以下两种方法之一：

第一种方法既最简单，又最快，但其他两种方法将在更复杂的应用程序中变得更加有趣，其中您想要连接字符串，但一步知道最终结果将是什么 less 明显。