C solution - O(n) time, O(1) space, only uses pointers/pointer arithmetic


  • 0
    C

    Here's an in place C solution that runs in O(n) time and O(1) space. Also, this solution only uses character pointers and pointer arithmetic; i.e., the length of string is not calculated and the string is not accessed via array indexing. This allows for very few local variables (two char pointers and an int flag.)

    The general algorithm used is:

    1. Eliminate excess whitespace in the string on one pass.
    2. Reverse the entire string by swapping the ith and ith to last characters.
    3. Reverse each word in the string using the same swapping method, but only on each word.

    String reversal is implemented using the XOR swapping trick.

    void reverse(char *s, char *e) {
    	// Swap characters *s and *e until s >= e (i.e., until the
    	// pointers meet in the middle of the string.)
    	// We swap using three successive XORs.
    	for (; s < e; ++s, --e) {
    		*s = *s ^ *e;
    		*e = *s ^ *e;
    		*s = *s ^ *e;
    	}
    }
    
    void reverseWords(char *s) {
    	char *c, *r;
    	// Flag indicating whether previous character was non-space character.
    	int nonspace_flag = 0;
    	// Consume excess whitespace in string by shifting characters to
    	// the beginning of the string, replacing the excess whitespace.
    	for (c = s, r = s; *r != '\0'; ++r) {
    		if (isspace(*r)) {
    		    // Only shift space character if previous character was not
    		    // a whitespace character.
    		    if (nonspace_flag) {
    		        *c++ = ' ';
    		        nonspace_flag = 0;
    		    }
    		}
    		else {
    		    *c++ = *r;
    		    nonspace_flag = 1;
    		}
    	}
    	// If s has at least one non-whitespace character and the nonspace_flag
    	// is still set after removing whitespace, then the final character that is
    	// pointed to by c is a space character.  In such a case, we replace this
    	// space character with the null terminating character.
    	c = (c != s && nonspace_flag == 0) ? c - 1 : c;
    	*c = '\0';  // Terminate the string.
    	
    	// Reverse the entire string.
    	reverse(s, c - 1);
    	
    	c = s;
    	// Reverse each word in the string.
    	while (*c != '\0') {
    	    ++c;
    	    // If at word boundary, reverse word.
    	    if (*c == '\0' || isspace(*c)) {
    	        reverse(s, c - 1);
    	        // Set s to the start of the next word.
    	        // NOTE:  This might set s to point to the byte of memory immediately
    	        //        following the end of the string.  However, this won't matter
    	        //        since, in such a case, *c == '\0', so this loop will exit
    	        //        before the next iteration, hence before s can be dereferenced.
    	        s = c + 1;
    	    }
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.