algorithm to reverse words of a string

This is a bit tricky algorithm and most frequently asked question in interviews. I will now show how to do it in the best time complexity of [O(2n)]. Complete source code can be downloaded from here.

Here we will make use of algorithm to reverse the string which is explained in our previous posts at O(n/2) complexity.

Steps to solve this algorithm

  • take two pointers, one pointing to the start of the array and another to the end of the array and swap the values at respective pointers.
  • While traversing the array increment starting pointer and decrement ending pointer and continue swap the values at respective pointers
  • continue this till we reach the middle of the array which will result in reversed string
  • from above generated reversed string take a pointer which runs through this string and stops at spaces which indicates the occurance of a word
  • go back to first three steps to reverse a word within this reversed string and go back to fourth step till the sentence is completed
  • by end of this algorithm, last word will not be reversed because there is no space after it and hence reverse the last word at the end

Source Code

	/**
	 * Algorithm to reverse word of a string
	 * @return reversed words array
	 */
	public char[] reverseWords(char[] arr) {
	    // reverse the string
	    reverse(arr, 0, arr.length / 2, arr.length);
	     
	    // reverse words of a string
	    int wordIdx = 0;
	    int wordMidIdx = 0;
	    int prevWordLastIdx = 0;
	 
	    // outer loop to track spaces
	    for (int sentenceIdx = 0; sentenceIdx < arr.length; sentenceIdx++) {
	        if (arr[sentenceIdx] != ' ')
	            continue;
	 
	        wordIdx = prevWordLastIdx;
	        int wordLastIdx = sentenceIdx;
	        wordMidIdx = (sentenceIdx + wordIdx) / 2;
	        // reverse each word in a string
	        reverse(arr, wordIdx, wordMidIdx, wordLastIdx);
	        prevWordLastIdx = sentenceIdx + 1;
	    }
	 
	    // reverse last word
	    wordIdx = prevWordLastIdx;
	    wordMidIdx = (arr.length + wordIdx) / 2;
	    reverse(arr, wordIdx, wordMidIdx, arr.length);
	     
	    return arr;
	}

How to arrive at the time complexity?

Step #1: reverse the complete string which is explained in our previous algorithm at O(n/2) complexity. https://tekmarathon.wordpress.com/2012/10/05/algorithm-to-reverse-a-string/

Step #2: keep a pointer which traverses through the string looking for spaces which takes O(n)

Step #3: using the above spaces reverse words within the string at O(n/2). Let us see why this is O(n/2)

'welcome to coding algorithms' would become 'smhtirogla gnidoc ot emoclew'

Now take the string 'smhtirogla gnidoc ot emoclew' and reverse each word within
 it with same logic explained in reversing the string. This will take O(n) 
 iterations, let us see how is it O(n)

At first iteration  
 'smhtirogla gnidoc ot emoclew' would become 'algorithms gnidoc ot emoclew' 
 at 5 iterations i.e (length of 'smhtirogla')/2)

At second iteration 
 'algorithms gnidoc ot emoclew' would become 'algorithms coding ot emoclew'
 at 3 iterations i.e (length of 'gnidoc')/2)

At third iteration  
 'algorithms coding ot emoclew' would become 'algorithms coding to emoclew'
 at 1 iterations i.e (length of 'ot')/2)

At fourth iteration 
 'algorithms coding to emoclew' would become 'algorithms coding to welcome'
 at 3 iterations i.e (length of 'emoclew')/2)

total length of the string = 29

total iterations = 12 + spaces = 15 (approximately half the length of the 
total string)

Total complexity from Step #1, Step #2 and Step #3 = O(n/2) + O(n) + O(n/2) = O(2n)

Complete source code can be downloaded from here.

Advertisements

One Response to algorithm to reverse words of a string

  1. Kavita says:

    Hi Niranjan,
    Nice program. Thank you for the simple logic and flow and illustration on code complexity.
    Since many a times, string reversal in place is asked without even using a temporary variable, I found an approach using xor on some website. Hence I changed the logic in reverse() to the foll:
    arr[wordIdx] ^= arr[wordLastIdx – 1];
    arr[wordLastIdx – 1] ^= arr[wordIdx];
    arr[wordIdx] ^= arr[wordLastIdx – 1];

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey