One pass solution with char[s.size()] + char pointer arithmetic 6~10ms


  • 0
    C

    The fastest solution I got:

    class Solution {
    public:
        void reverseWords(string &s) {
            const int len = s.size();
            if (len==0)
                return; // empty string
            const char *sp = s.c_str();
            char *rstr = new char[len+1] ; // allocate for new string
            char *rsp = rstr;
            int i, wstart, wend; // original string pointers
            for(i = wend= len, wstart=0; i> 0; --i) {
                while (i && is_space(sp[i-1])) --i; // find word end
                if (i==0)
                    break; // leading spaces in the string
                wend = i-1;
                while (i && !isspace(sp[i-1])) --i; // find word start
                wstart = i;
                for (int j= wstart; j<=wend; ++j) *rsp++ = sp[j]; // copy
                *rsp++ = ' '; // word separator
            }
            *(--rsp) = '\0'; // remove last space + terminate string
            s = rstr;
            delete rstr;
        }
        inline bool is_space(const char ch) {
            return (ch== ' ' || ch=='\t' || ch=='\n' || ch=='\v' || ch=='\f' || ch=='\r');
        }
    };

Log in to reply
 

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