Reverse and Reverse Again, Accepted In-place Solution in C


  • 0
    S
    void reverseWords(char *s) {
        int len = strlen(s);
        int start = 0, l = 0, r;
        char *l_ptr, *r_ptr;
        
        while (s[start] != '\0') {
            // find a word
            for (; len > l && s[l] == ' '; ++l);
            if (len == l) break;
    
            for (r = l + 1;len > r && s[r] != ' '; ++r);
            
            // Reverse a single word
            l_ptr = s + l;
            r_ptr = s + r - 1;
            for (; l_ptr < r_ptr; ++l_ptr, --r_ptr) {
                char c = *l_ptr;
                *l_ptr = *r_ptr;
                *r_ptr = c;
            }
            
            // Trim spaces
            if (start != l) {
                // Yes, memmove accepts overlapped memory areas
                memmove(s + start, s + l, r - l);
                memset(s + start + r - l, ' ', l - start);
            }
            
            start += r - l + 1;
            l = start;
        }
        
        // Trim trailing spaces
        for (; len > 0 && s[len - 1] == ' '; --len);
        s[len] = '\0';
        
        // Reverse while string
        l_ptr = s;
        r_ptr = s + len - 1;
        for (; l_ptr < r_ptr; ++l_ptr, --r_ptr) {
            char c = *l_ptr;
            *l_ptr = *r_ptr;
            *r_ptr = c;
        }
    }
    

  • 0
    S

    Better one.

    void reverseWords(char *s) {
        int len = strlen(s);
        int start = 0, l = 0, r;
        char *l_ptr, *r_ptr;
        
        while (s[start] != '\0') {
            for (; len > l && s[l] == ' '; ++l);
            if (len == l) break;
    
            for (r = l + 1;len > r && s[r] != ' '; ++r);
            
            l_ptr = s + start;
            r_ptr = s + r - 1;
            for (; l_ptr < r_ptr; ++l_ptr, --r_ptr) {
                char c = *l_ptr;
                *l_ptr = *r_ptr;
                *r_ptr = c;
            }
            
            start += r - l + 1;
            l = start;
        }
        
        for (; len > 0 && s[len - 1] == ' '; --len);
        s[len] = '\0';
        
        l_ptr = s;
        r_ptr = s + len - 1;
        for (; l_ptr < r_ptr; ++l_ptr, --r_ptr) {
            char c = *l_ptr;
            *l_ptr = *r_ptr;
            *r_ptr = c;
        }
    }
    

Log in to reply
 

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