For C programmers


  • 0
    K

    Clarification:

    * What constitutes a word? A sequence of non-space characters constitutes a word.
    * Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces.
    * How about multiple spaces between two words? Reduce them to a single space in the reversed string.
    

    code:

    void reverse(char* s, int start, int end){
        char t;
        for(;start<end;start++,end--){
            t = s[start];
            s[start] = s[end];
            s[end] = t;
        }
    }
    void reverseWords(char *s) {
        if(s == NULL){
            return;
        }
        int n = strlen(s);
        int i = 0, j = strlen(s) - 1, t = 0, r = 0;
    
        while(s[j] == ' '){
            s[j] = '\0';
            j -= 1;
        }
        while(s[i] == ' '){
            i++;
        }
        n = strlen(s);
        r = t + i;
        while(n > 0){
            while(s[r] == ' ' && s[r+1] == ' '){
                r++;
            }
            s[t] = s[r];
            t++;
            r++;
            n--;
        }
        s[t] = '\0';
        i = 0;
        n = strlen(s);
        while(i < n){
            j = i;
            while(j < n){
                if(s[j] == ' '){    
                    break;
                }else{
                    j++;
                }
            }
            reverse(s, i, j-1);
            while(j < n && s[j] == ' '){
                j++;
            }
            i = j;
        }
        reverse(s, 0, n - 1);
    }
    

  • -1

    @Kosmos This code writes a little ugly!


  • 0
    K

    @cpselvis I was a newbie, please do not mind.


  • -1

    I write a c++ version, may inspire you.

    class Solution {
    public:
      void reverseWords(string &s) {
        stripSpaces(s);
        reverse(s.begin(), s.end());
        int i, j;
        for (i = 0, j =  0; j < s.size(); j ++ )
        {
          if (s[j] == ' ')
          {
    	reverse(s.begin() + i, s.begin() + j);
    	i = j + 1;
          }
        }
        reverse(s.begin() + i, s.end());
      }
      void stripSpaces(string &s)
      {
        // Remove leading spaces before a string
        while(s.size() > 0 && s[0] == ' ')
        {
          s.erase(0, 1);
        }
        s += ' ';
        // Remove center space
        for (int i = 0; i < s.size(); i ++)
        {
          while (s[i] == ' ' && s[i + 1] == ' ')
          {
    	s.erase(i, 1);
          }
        }
        // Remove last space
        s.erase(s.size() - 1, 1);
      }
    };
    

  • 0

    @Kosmos Refactored your solution in C as follows:

    void reverse(char* s, int begin, int end){
        while(begin < end){
            char t = s[begin];
            s[begin] = s[end];
            s[end] = t;
            begin++, end--;
        }
    }
    bool isValid(char c){
        return !isblank(c) && c!='\0';
    }
    
    void removeExtraSpace(char* s){
        int out = 1, index = 0;
        for(int i = 0; s[i]; ++i){
            if(isValid(s[i])) s[index++] = s[i], out = 0;
            else {
                if(!out) s[index++] = s[i]; 
                out = 1;
            }
        }
        s[index] = '\0';
    }
    void reverseWords(char *s) {
        int len = strlen(s), i = len-1;
        while(s[i] == ' ') s[i--] = '\0';
        reverse(s, 0, strlen(s)-1);
        i = strlen(s)-1;
        while(s[i] == ' ') s[i--] = '\0';
        removeExtraSpace(s);
        int start = 0, out = 0;
        i = 0, len = strlen(s);
        while(i <= len){
            if(isValid(s[i]) && out) out = 0, start = i;
            if(!isValid(s[i]) && !out) out = 1, reverse(s, start, i-1);
            i++;
        }
    }
    

  • 0

    @cpselvis C++ can do far better actually.


Log in to reply
 

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