Share my two C++ solutions, easy to understand


  • 2
    V

    O(1) space

    class Solution {
    public:
        void reverseWords(string &s) {
            int len = s.length();
            if (len == 0)
                return;
            
            int i = 0;
            int j = len - 1;
            int cnt = 0;
            
            while (i < len && s[i] == ' ')
                i++;
            if (i == len)
            {
                s = "";
                return;
            }
            while (j >=0 && s[j] == ' ')
                j--;
                
            s = s.substr(i, j - i + 1);//delete the leading or trailing spaces
            len = s.length();
            
            i = 0;
            j = 0;
            while (i < len)//change multiple spaces between two words to a single space
            {
                s[j] = s[i];
                j++;
    
                if (s[i] != ' ')
                    i++;
                else
                {
                    while (i < len && s[i] == ' ')
                        i++;
                }
            }
            len = j;
            s = s.substr(0, len);
            my_reverse(s, 0, len-1);
            
            i = 0;
            j = 0;
            while (i < len)
            {
                while (i < len && s[i] != ' ')
                    i++;
                
                my_reverse(s, j, i-1);
                
                if (i < len)
                    j = i + 1;
                i++;
            }
        }
        
        void my_reverse(string &s, int start, int end)
        {
            while (start < end)
            {
                char ch = s[start];
                s[start] = s[end];
                s[end] = ch;
                
                start++;
                end--;
            }
        }
    };
    

  • 0
    V

    O(n) space

    class Solution {
    public:
        void reverseWords(string &s) {
            int len = s.length();
            if (len == 0)
                return;
            
            string sentence;
            int i = len - 1;
            
            while (i >= 0)
            {
                while (i >= 0 && s[i] == ' ')
                    i--;
                if (i < 0)
                    break;
                    
                string word;
                while (i >= 0 && s[i] != ' ')
                {
                    word.push_back(s[i]);
                    i--;
                }
                reverse(word.begin(), word.end());
                if (!sentence.empty())
                    sentence.push_back(' ');
                sentence.append(word);
            }
            
            s = sentence;
        }
    };
    

Log in to reply
 

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