c++ - 反转字符数组中单词的顺序

Question

要注意的是特殊字符的位置(例如:'?'、','、''、'.')应该保持不变。所以对于输入字符串“Hello World，你好吗？”输出将是“you are, how World Hello?”。现在对于没有特殊字符的字符串，O(n) 算法是将每个单词反转，然后反转整个数组，但不考虑特殊字符。

我想出的最佳算法如下。我们遍历数组并将每个单词压入堆栈顶部，然后将特殊字符放入队列中。稍后，我们同时从堆栈和队列中弹出元素，并将它们连接起来以形成所需的输出。

是否有就地 O(n) 算法？如果没有，您能否建议一个没有额外空间的 O(n^2) 算法。还假设您不能使用任何字符串库函数。

Answer 1

所以，这是一个想法。

1) 初始字符串

"Hello World, how are you?"

2) 反转字符串，但不包含任何最后的特殊字符

"uoy era woh ,dlroW olleH?"

3) 反转字符串中的单词

"you are how ,World Hello?"

4) 创建一个指向字符串开头和结尾的迭代器(指针、索引，无论您使用什么)，递增/递减每个迭代器，直到它们命中非单词。非文字是指空格或特殊字符。因此，在这种情况下，递增迭代器将首先遇到“you”和“are”之间的空格，而递减迭代器将遇到“world”和“Hello”之间的空格，如下所示。

"you are how ,World Hello?"
    ^              ^

5) 如果没有特殊字符，继续，如果你打了一个特殊字符。反转迭代器之间的所有内容，包括它们指向的字符。下面显示了这种情况发生的时间

"you are how ,World Hello?"
        ^    ^

6) 现在我们看到了反转的结果。

"you are, woh World Hello?"

根据 johnchen902 的评论进行编辑

7) 现在反转这些迭代器之间的子字符串，不包括在步骤 (5) 中找到的特殊字符。

"you are, how World Hello?"

8) 返回步骤(5)

我还没有编写代码，解释起来有点棘手，但我希望你能理解