0ms in-place C solution in O(1) space.


  • 0
    M
    //reverse one word
    inline void reverseWord(char *s, int len){
       char c;
       int i , j;
       for(i = 0, j = len -1 ;i<j;++i,--j){
         c=s[i];
         s[i]=s[j];
         s[j]=c;
       }
    }
    extern void reverseWord(char *s, int len);
    
    void reverseWords(char *s) {
        int len = strlen(s);
        char *start = s;
        char *end = start + len - 1;
    
        for (; *start == ' '; ++start);
        for (; *end == ' '; --end);
    
        if (start > end) {
            s[0] = 0;
            return;
        }
    
        int size = ++end - start ;
        
        reverseWord(start,size);
        char *p1=start,*p2=start;
        char *dest = s;
        size = 0;
        int n = 0;
        while(p2<=end){
            ++p2;
            if(*p2==' ' || p2 >=end){
                //p1=>p2-1 is a reversed word
                n = p2 - p1;
                reverseWord(p1,n);
                ++n; //space
                size+=n;
                strncpy(dest,p1,n);
                dest+=n;
                
                //accept one space
                ++p2;
                //if there are more spaces, skip them
                for(;*p2 == ' ' && p2 <=end;++p2);
                p1=p2;
            }
        }
        
        s[--size]=0;
    }

Log in to reply
 

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