Reverse Words in a String

Reverse the order of words in a string "jackdaws love my big sphinx of quartz" to "quartz of sphinx big my love jackdaws"

Solution 1: Using a Stack
Assumption: The string literal is given in a String

public String reverseString(String myStr)
{
String [] myStrSplit = myStr.split("-");
Stack<String> stack = new Stack<String>();
StringBuilder myStrReverse = new StringBuilder();

for ( String s : myStrSplit )
{
stack.push( s );
}

while ( !stack.empty() )
{
myStrReverse.append( stack.pop() );
}

return myStrReverse.toString();
}


Time Complexity
String#split + pushing on stack + popping off stack
N + N + N time
= O( 3N )

Space Complexity
myStr + myStrSplit + stack + myStrReverse
N + N + N + N
= O( 4N )

Solution 2: Using a Doubly LinkedList

public void reverseString(DLinkedList myStr)
{
Node next, prev;

for ( Node n : myStr )
{
next = n.next;
prev = n.prev;

n.next = prev;
n.prev = next;
}
}

Time Complexity
traverse myStr
= O( N )

Space Complexity
Space for next and prev
= O( 1 ) (constant space)

Solution 3: Using XOR

#include <cstdio>
#include <cstdlib>
#include <iostream>


using namespace std;


// Find next space position
inline int nextSpacePosition(char *str, int startPosition)
{
int nextSpacePosition = -1;


for ( int i = startPosition; str[i] != '\0'; ++i )
{
if ( str[i] == ' ' )
{
nextSpacePosition = i;
break;
}
}


return nextSpacePosition;
}


// XOR Swap
inline void swap(char *a, char *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}


int main(int argc, char **argv)
{
char *originalStr = "jackdaws love my big sphinx of quartz";
char reverseStr[256];
int strLength;
int pos, spacePos;
bool lastIteration = false;

pos = 0;
spacePos = 0;
strcpy(reverseStr, originalStr);
strLength = strlen(reverseStr);


// Reverses string
for ( int i = 0; i < strLength/2; ++i )
{
swap(reverseStr[i], reverseStr[strLength-i-1]);
}


// Reverses words
while ( ! lastIteration )
{
// Find where word ends (space)
spacePos = nextSpacePosition( reverseStr, spacePos+1 );


if ( spacePos == -1 )
{
spacePos = strLength;
lastIteration = true;
}


// Reverse word
int end = pos + ((spacePos-pos) / 2);
for ( int i = pos; i < end; ++i )
{
swap( reverseStr[i], reverseStr[spacePos-1-(i-pos)] );
}


pos = spacePos + 1;
}


cout << "Original: " << originalStr << endl;
cout << "Reversed: " << reverseStr << endl;
}

Time Complexity

traverse half of reverseStr (reversing the string) + traverse reverseStr (reversing words) + string length

= O( 5/2 * N )

= O( N )

Space Complexity

Space for constant space variables

= O( 1 ) (constant space)

The appealing feature for this method is that it doesn't require any "new" data structures (i.e., linked list) and all the work is done in place.