颠倒字符数组中单词的顺序

Question

问题在于特殊字符的位置(例如:'？',',','','.')应保持不变.所以对于输入字符串"Hello World,你好吗？" 输出将是"你是,世界你好？".现在对于没有特殊字符的字符串,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)创建一个迭代器(指针,索引,无论你使用什么)到字符串的开头和结尾,增加/减少每个迭代器,直到它们击中非单词.非单词我指的是空格或特殊字符.所以在这种情况下,增加的迭代器首先会遇到'你'和'是'之间的空白,而减少的迭代器会遇到'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).

我还没有对此进行编码,解释起来有点棘手,但我希望你理解