09/04/2018

[Java] Reverse words in char array

Given an array of characters representing a text with words separated by a single space, reverse the text. Eg:

{'c', 'a', 's', 'e', ' ', 't', 'e', 's', 't', ' ', 'm', 'y'}

should read "my test case" in output.

This can be done in constant O(1) space by handling the array in place and in O(N) time.

The idea is to reverse the full array first, then find each word (they are delimited by a space) and reverse them in place again. So:

{'c', 'a', 's', 'e', ' ', 't', 'e', 's', 't', ' ', 'm', 'y'}

becomes

{'y', 'm', ' ', 't', 's ', 'e', 't', ' ', 'e', 's', 'a', 'c'}

and finally

{'m', 'y', ' ', 't', 'e', 's', 't', ' ', 'c', 'a', 's', 'e'}

The key point is to track where did we arrive with each word reversal so that we actually keep the runtime linear, I would say it is exactly 3N, once for reversing the full array, once for scanning the array while finding the delimiters and once for reversing each word starting and ending at the marked indexes.

You can check my implementation of reverseWords on my Gist alongside some test cases in ReverseWordsJTests.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.