C++ O(1) space


  • 0

    In-place.

    class Solution {
    public:
        void reverseWords(string &s) {
            // Reverse string
            reverse(s.begin(), s.end());
            // Reverse every word
            int i = 0, j = 0;
            while(i != s.size()){
                while(j < s.size() && s[j] != ' ') j++;
                reverse(s.begin() + i, s.begin() + j);
                i = j;
                while(i < s.size() && s[i] == ' ') i++, j++;
            }
            // Remove extra ' '
            i = 0, j = 0;
            while(j < s.size()){
                bool new_word = false;
                while(j < s.size() && s[j] == ' '){
                    new_word = true;
                    j++;
                }
                if(j == s.size()) break;
                if(new_word && i > 0) s[i++] = ' ';
                s[i++] = s[j++];
            }
            s = s.substr(0, i);
        }
    };
    

    And with extra space.

    class Solution {
    public:
        void reverseWords(string &s) {
            string res = "";
            string word = "";
            int j = 0;
            for(int i = 0; i < s.size(); i++){
                while(s[i] == ' ') i++;
                j = i;
                while(s[j] != ' ') j++;
                word = s.substr(i, j - i);
                if(res != "" && word != "") word += " ";
                res = word + res;
                i = j;
            }
            s = res;
        }
    };
    

Log in to reply
 

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