C++ O(N) Time In-place Solution


  • 2
    // OJ: https://leetcode.com/problems/reverse-words-in-a-string-iii
    // Auther: github.com/lzl124631x
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
      string reverseWords(string s) {
        int begin = 0;
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || isspace(s[i])) {
                reverse(s.begin() + begin, s.begin() + i);
                begin = i + 1;
            }
        }
        return s;
      }
    };
    

    BTW, if without the condition,

    Note: In the string, each word is separated by single space and there will not be any extra space in the string.

    the code can be as follows

    // OJ: https://leetcode.com/problems/reverse-words-in-a-string-iii
    // Auther: github.com/lzl124631x
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
      string reverseWords(string s) {
        int begin = 0;
        while (begin < s.size() && isspace(s[begin])) ++begin;
        while (begin < s.size()) {
          int end = begin;
          while (end < s.size() && !isspace(s[end])) ++end;
          reverse(s.begin() + begin, s.begin() + end);
          begin = end;
          while (begin < s.size() && isspace(s[begin])) ++begin;
        }
        return s;
      }
    };
    

Log in to reply
 

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