C 3ms in-place O(n) time & O(1) space solution


  • 0

    Steps:

    1. reverse each word and ignore the leading spaces and extra spaces
    2. reverse the whole string
    void reverseWords(char *s) {
        // fprintf(stderr, "\"%s\" -> ", s);
        int len = strlen(s);
        int iRet = 0;
        int i, j;
        
        // reverse each word
        for (i = 0; i < len; i ++) {
            while (i < len && s[i] == ' ') i ++;
            int beg = i;
            while (i < len && s[i] != ' ') i ++;
            int end = i;
            
            if (beg == end) break; // last one
            else {
                // swap between
                end --;
                int end_bak = end, beg_bak = beg;
                while (beg < end) {
                    int temp = s[beg];
                    s[beg] = s[end];
                    s[end] = temp;
                    beg ++;
                    end --;
                }
                
                // copy to the front
                while (beg_bak <= end_bak) {
                    s[iRet ++] = s[beg_bak ++];
                }
                s[iRet ++] = ' ';
            }
        }
        s[iRet > 0 ? iRet - 1 : 0] = '\0';
        // fprintf(stderr, "\"%s\" ", s);
        
        // reverse the string
        len = strlen(s);
        // fprintf(stderr, "(%d) -> ", len);
        i = 0, j = len - 1;
        while (i < j) {
            int temp = s[i];
            s[i ++] = s[j];
            s[j --] = temp;
        }
        // fprintf(stderr, "\"%s\"\n", s);
    }
    

Log in to reply
 

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