C++, In place, without using APIs, with explanation


  • 0
    M

    Because we only need to reverse each word within their space, the time complexity should be O(N) and space complexity should be O(1).

    Every time we need to locate a word's location, with begin and end.
    Therefore we can reverse one word just using the old method.
    While end is the first time out of bound, we reverse the last word and jump out of the while loop.
    Everything is done.

        string reverseWords(string s) {
            if (s.empty()) return s;
            size_t begin = 0, end = 0;
            while (end < s.size()) {
                while (s[end] != ' ' && end < s.size()) {
                    ++end;
                }
                for (size_t i = begin; i < (begin + end) / 2; ++i) {
                    char temp = s[i];
                    s[i] = s[begin + (end - i) - 1];
                    s[begin + (end - i) - 1] = temp;
                }
                ++end;
                begin = end;
            }
            return s;
        }
    

Log in to reply
 

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