o(1) space c++ solution, longer code but clear logic


  • 0
    G

    The basic idea is reverse the total string first, and then reverse each word in the string. We need to pay attention to the possible multiple spaces. In this case, we treat the string to make it has only one space between words, and delete all heading and trailing spaces.

       void reverseWords(string &s) {
        if (s.empty()) {
            return;
        }
        
        rev(s, 0, s.size()-1);
        prep(s);
        
        int l = 0, r = 0;
        int n = s.size();
        while (l < n) {
            while (l < n && s[l] == ' ') {
                l++;
            }
            
            r = l;
            while (r < n && s[r] != ' ') {
                r++;
            }
            
            rev(s, l, r-1);
            l = r;
        }
        
        return;
    }
    
    void rev(string &s, int l, int r) {
        while (l <= r) {
            swap(s[l++], s[r--]);
        }
    }
    
    void prep(string &s) {
        while (!s.empty() && s[0] == ' ') {
            s.erase(s.begin());
        }
        
        while (!s.empty() && s.back() == ' ') {
            s.erase(s.end() - 1);
        }
        
        int i = 1;
        while (i < s.size()) {
            if (s[i-1] == ' ' && s[i] == ' ') {
                s.erase(s.begin() + i);
            }
            else {
                i++;
            }
        }
    }

Log in to reply
 

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