O(n) Time and Space, but readable!


  • 0
    B

    Re: Accepted simple cpp code in just a few lines Same idea, going from back to front, to avoid inserting elements at the beginning of the result string, so we have O(n) time, though still O(n) space. But I like how readable it is!

    void reverseWords(string &s) {
            string result;
            int n=s.length(),p=n-1,i=n-1;
            
            for (; i>=0; i--) {
                if (s[i]==' ') {
                    if (i<p) result+=s.substr(i+1,p-i)+' ';
                    p=i-1;
                }
            }
            
            if (i<p) result+=s.substr(i+1,p-i)+' ';
            
            // remove trailing ' ', if any
            s = result.substr(0,result.size()-1);
        }
        
    

Log in to reply
 

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