Java Solution with O(n) Space


  • 0
    A

    1 iteration but with O(n) memory.

    /**
     * move from right to left, find each word;
     * then append the chars of word from eft to right into a stringbuilder;
     * insert single space between words on stringbuilder.
     */
    public String reverseWords(String s) {
        StringBuilder builder = new StringBuilder();
        int right = s.length() - 1;
        while (right >= 0) {
            while (right >= 0 && s.charAt(right) == ' ')
                right--;
            if (right < 0)
                break;
            int left = right - 1;
            while (left >= 0 && s.charAt(left) != ' ')
                left--;
            if (builder.length() > 0)
                builder.append(' ');
            for (int i = left + 1; i <= right; i++)
                builder.append(s.charAt(i));
            right = left;
        }
        return builder.toString();
    }

Log in to reply
 

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