In-place Java solution with comments just for fun


  • 15
    S

    Hi guys!

    Just to keep it more interesting made it in-place in Java without using any additional library functions except converting String to char[]. Check it out. :)

    // reverses the part of an array and returns the input array for convenience
    public char[] reverse(char[] arr, int i, int j) {
        while (i < j) {
            char tmp = arr[i];
            arr[i++] = arr[j];
            arr[j--] = tmp;
        }
        return arr;
    }
    
    public String reverseWords(String s) {
        // reverse the whole string and convert to char array
        char[] str = reverse(s.toCharArray(), 0, s.length()-1);
        int start = 0, end = 0; // start and end positions of a current word
        for (int i = 0; i < str.length; i++) {
            if (str[i] != ' ') { // if the current char is letter 
                str[end++] = str[i]; // just move this letter to the next free pos
            } else if (i > 0 && str[i-1] != ' ') { // if the first space after word
                reverse(str, start, end-1); // reverse the word
                str[end++] = ' '; // and put the space after it
                start = end; // move start position further for the next word
            }
        }
        reverse(str, start, end-1); // reverse the tail word if it's there
        // here's an ugly return just because we need to return Java's String
        // also as there could be spaces at the end of original string 
        // we need to consider redundant space we have put there before
        return new String(str, 0, end > 0 && str[end-1] == ' ' ? end-1 : end);
    }
    

    Have a nice coding there!


  • 0
    C

    Excellent and clean!
    I added 's = " " + s;' at the beginning of the program so that we don't have to do the extra 'reverse(str, start, end-1);' after the for loop.


  • 0
    B
    This post is deleted!

  • 0
    T

    you can make the last line less ugly by defining end to be really the end of the seen part of a word. to do this you need to change the line with comment "and put the space after it" and remove the "++", and only update end when u see the next non-white char, by adding a check before the line "just move this letter to the next free pos", if (end < start) end = start;

    right now your "end" var actually refers to "the next position to write a char", which could be either a white space , or a non-white. only in the latter case does it really mean "end".

    I used 2 vars , end, and "nextNonWhite" in my earlier version for clarity


  • 0
    L

    This is technically not in place as strings in Java are immutable. But this is how one would do it in C, so nice.


  • 0
    B

    @lekzeey he already converted it to an array so it is actually in place


Log in to reply
 

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