My 0ms O(1) space C solution with explanation


  • 1
    A

    Reverse whole string and then reverse each word.
    word here means word with leading spaces but without trailing spaces (e.g. ' blue')
    When reversing word, the leading spaces will become the leading spaces of next word, be caution to move back the left index.

    I think my code is sufficiently self-explaining

    void reverseString(char *s, int i, int j) {
        int temp;
        while (i < j) {
            temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++; j--;
        }
    }
    
    void reverseWords(char *s) {
        int i, j, len; 
        // find length
        i = 0;
        while (s[i]) 
            i++;
        len = i;
    
        // special case for size 0 and 1 
        if (len == 0)
            return;
        if (len == 1) {
            if (s[0] == ' ')
                s[0] = '\0';
            return;
        }
        
        // trim trailling space, and reverse whole string
        i = len - 1;
        while (i >= 0 && s[i] == ' ')
            i--;
        reverseString(s, 0, i);
    
        // reverse each `word` (may with leading space but no trailling space)
        // j is right index and i is left index
        j = 1; i = 0;
        while (s[j]) {
            // find  word end
            while (s[j] != '\0' && s[j] != ' ')
                j++;
            // reverse word
            reverseString(s, i, j-1);
            
            // reversed `word` with leading spaces will introduce more leading space for next word
            // so move back left index
            i = j;
            while (i > 0 && s[i-1] == ' ')
                i--;
            i++; // one space between `word`
            
            // right index points to the begining of next word 
            while (s[j] != '\0' && s[j] == ' ')
                j++;
        }
    
        // trim leading spaces of the string
        while (j > 0 && s[j-1] == ' ')
            j--;
        s[j] = '\0';
    }

Log in to reply
 

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