c++ solution O(n) time complexity O(1) space complexity


  • 0
    T
    class Solution {
    public:
    	void reverse(string &s, int l, int r) {
    		while (l < r) swap(s[l++], s[r--]);
    	}
    	void reverseWords(string &s) {
    		int w = 0, r = 0, sz = s.size();
    		while (r < sz) {
    			if (s[r] == ' ') {
    				++r;
    				if (w - 1 >= 0 && s[w - 1] != ' ' && r < sz) s[w++] = ' '; // if not added space
    			}
    			else s[w++] = s[r++];
    		}
    
    		s.resize(w);
    		if (s.back() == ' ') s.resize(s.size() - 1); // remove possible space at the end of string
    		w = r = 0, sz = s.size();
    		while (r < sz) {
    			while (r < sz && s[r] != ' ') ++r;
    			reverse(s, w, r - 1);
    			while (r < sz && s[r] == ' ') ++r;
    			w = r;
    		}
    		reverse(s, 0, sz-1);
    	}
    };
    

Log in to reply
 

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