CODEWITHSUNDEEP
c++stringalgorithm
user2560730
user2560730

Reputation: 345

Reversing the order of words in a character array

The catch being that the position of special characters (for eg: '?' , ',' , ' ' , '.') should remain intact. So for an input string "Hello World, how are you?" The output would be "you are, how World Hello?". Now for the string without special characters, the O(n) algorithm is to reverse each word and then reverse the entire array, but that doesn't take into consideration the special characters.

The best algorithm I came up with is as follows. We traverse the array and push each word on top of the stack and then enqueue the special characters on a queue. And later, we pop elements from stack and queue simultaneously and conjoin them to form the required output.

Is there an in-place O(n) algorithm? If not, can you suggest an O(n^2) algorithm with no extra space. Also assume, you cannot use any string library functions.

Upvotes: 4

Views: 1477

Answers (2)

Muckle_ewe
Muckle_ewe

Reputation: 1123

So, here's an idea.

1) Initial string

"Hello World, how are you?"

2) Reverse string, but do not include any final special characters

"uoy era woh ,dlroW olleH?"

3) Reverse words in string

"you are how ,World Hello?"

4) Create an iterator (pointer, index, whatever you use) to the start and the end of the string, increment/deincrement each iterator until they hit non-words. By non words I mean blank space or a special character. So in this case, the increasing iterator would first come across the blank between 'you' and 'are', while the decreasing iterator would come across the blank space between 'world' and 'Hello' as shown below. 

"you are how ,World Hello?"
    ^              ^

5) If there are no special characters, continue, if you hit a special character however. Reverse everything between the iterators, including the characters they point to. Below shows when this happens

"you are how ,World Hello?"
        ^    ^

6) And now we see the result of reversing this.

"you are, woh World Hello?"

Edit due to comment from johnchen902

7) Now reverse 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 coded this yet and it was slightly tricky to explain but I hope you understand

Upvotes: 5

Keldon Alleyne
Keldon Alleyne

Reputation: 2130

For an in-place algorithm simply create two iterators (that iterate on words), one reverse iterator and the other going forward.

Your loop will simply consist of something like:

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 have to create your own simple word iterator for this logic to work, but that's easy enough to achieve.

Upvotes: 1

Related Questions