Java concise in-place solution.


  • 11
    C
    public void reverseWords(char[] s) {
        reverse(s, 0, s.length-1);  // reverse the whole string first
        int r = 0;
        while (r < s.length) {
            int l = r;
            while (r < s.length && s[r] != ' ')
                r++;
            reverse(s, l, r-1);  // reverse words one by one
            r++;
        }
    }
    
    public void reverse(char[] s, int l, int r) {
        while (l < r) {
            char tmp = s[l];
            s[l++] = s[r];
            s[r--] = tmp;
        }
    }

  • 0

    @caikehe

    The problem statement says "Could you do it in-place without allocating extra space?"
    Not sure if char tmp allowed.


  • 2

    @zzhai a fixed number of variables are considered "constant" space as opposed to space that depends on the size of the inputs. Anything that increases as the size of the inputs increase counts as "extra space" and you'll see it quantified using big-O notation, like O(n) extra space or O(1) constant space. So, this solution does not use extra space.


  • 0
    M

    @jdrogin Then, what's the difference between this problem and Problem 151. "Reverse Words in a String" regardless of leading or trailing space?


  • 0

    @MichaelZ205

    In 151, the input is a string, which cannot be easily reversed without extra space for programming languages other than C.
    In this problem, input is a char array that can.


  • 0
    H

    @MichaelZ205 In Java, string is immutable. Every modification on the string will create a new copy of string so there is technically no "in-place" solution for programming languages other than C.


  • 0
    W

    Can you please help me understand complexity of this inplace solution.

    Thanks


  • 0
    G

    @zzhai constant space is not included, when somebody asks not to use extra space. If you think carefully, for looping constructs too we create variables.


Log in to reply
 

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