如何在O(1)复杂度(运行时)中反转字符串？

Question

我今天接受了采访,并被要求在一次操作中反转一个字符串.我感觉不到O(n)就不可能了.顺便说一句,我有一个线索," 交换 "!所以...有答案吗？

• 示例输入:"abcdefghi"(或任何字符串)
• 样本输出:"ihgfedcba"
• 不能使用内置功能.(例如:strrev())
• 答案并不像反向打印/迭代那样棘手.

Answer 1

您无法在时间上反转字符串O(1)，但是可以通过O(1)空间复杂度来实现。

在单个操作中反转字符串

最有可能的是reverse it in one-liner，因为甚至不清楚“操作”到底是什么。

您可以使用std::reverse算法在一行中反转字符串：

#include <string>
#include <algorithm>

int main()
{
    std::string str = "Hello world!";
    std::reverse(str.begin(), str.end());
    std::cout << "reverse is: \"" << str << '\"' << std::endl;
}

输出：

reverse is: "!dlrow olleH"

或者你也可以使用一个简单的循环来做到这一点：

for (size_t i=0; i<str.size()/2; ++i)
    std::swap(str[i], str[str.size()-1-i);

然而，这是O(N)运行时和O(1)空间（就像std::reverse）。

通常，简单的反向字符串算法问题的面试与一些技巧无关，很可能你的面试官希望看到这种循环的实现。另外，不要忘记面试官也是人，有时他们只是会犯错误并提出不可能的要求。或者，他们只是想让你说不可能反转 中的序列O(1)。

Answer 2

反转字符串？只需从rbegin()迭代到rend(). 或者std::copy该范围为新字符串。“反转字符串”与原始字符串完全相同，只是以相反的方式读取。