Reverse word order in an array of characters

Question

The trick is that the position of special characters (for example, "?", ",", ",". ") Must remain unchanged. So, for the input string" Hello World, how are you? “The output will be“ you, like World Hello? ”. Now for a string without special characters, the O (n) algorithm should cancel each word and then change the entire array, but this does not take into account special characters.

The best algorithm I came up with is the following. We move the array and push each word on top of the stack, and then put the special characters in the queue. And later, we populate the items from the stack and the queue at the same time and connect them to form the required output.

Is there a proprietary O (n) algorithm? If not, can you suggest an O (n ^ 2) algorithm without extra space. Also suppose that you cannot use any functions of string libraries.

Answer 1

So here is the idea.

1) Start line

"Hello World, how are you?" 

2) Return line, but not including final special characters

 "uoy era woh ,dlroW olleH?" 

3) Inverse words in a string

 "you are how ,World Hello?" 

4) Create an iterator (pointer, index, whatever you use) at the beginning and end of the line, increase / decrease each iterator until you hit non-words. Without words, I mean a space or a special character. Thus, in this case, the incrementing iterator will first encounter a space between “you” and “there”, while the decreasing iterator will encounter an empty space between the “world” and “Hello”, as shown below.

 "you are how ,World Hello?" ^ ^ 

5) If there are no special characters, continue if you press the special character. Flip everything between iterators, including the characters they point to. The following shows when this happens.

 "you are how ,World Hello?" ^ ^ 

6) And now we see the result of reversing.

 "you are, woh World Hello?" 

Edit due to comment from johnchen902

7) Now we will reverse the substring between these iterators, excluding the special character found in step (5).

 "you are, how World Hello?" 

8) return to step (5).

I haven't encoded this yet, and it was a bit hard to explain, but I hope you understand

Answer 2

For a local algorithm, simply create two iterators (iterating over words), one reverse iterator and the other forward.

Your cycle will only consist of:

 while(FirstIteratorIsBefore(forward_iterator, backward_iterator)) { if(IsSpecialCharacter(*forward_iterator)) { ++forward_iterator; } else if(IsSpecialCharacter(*backward_iterator)) { ++backward_iterator; } else { // Swap the two Swap(forward_iterator, backward_iterator); ++forward_iterator; ++backward_iterator; } } 

Note. You will need to create your own simple word iterator for this logic to work, but this is fairly easy to achieve.