# Reverse Words in a String Given an input string, reverse the string word by word. **Example:** ``` Input: "the sky is blue", Output: "blue is sky the". ``` **Note:** * A word is defined as a sequence of non-space characters. * Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces. * You need to reduce multiple spaces between two words to a single space in the reversed string. **Follow up:** For C programmers, try to solve it*in-place\_in\_O*(1) space. **Topics**: Two Pointers, String ## Analysis It actually reminds me of the [string rotation problem](https://leetcode.com/problems/rotate-string/) , which could be solved by multi-step reversal of the string as well. The function `void reverseWords(char[] a, int n)`, which is very much similar to what could be used in [Max Consecutive Ones](https://leetcode.com/problems/max-consecutive-ones/) problem. > **Two Pointers to the MAX.** ### Multi-reversal ```java // step 1. clean up spaces char[] a = cleanSpaces(c, m); int n = a.length; // step 2. reverse the whole string reverse(a, 0, n - 1); // step 3. reverse each word reverseWords(a, n); ``` The `void reverseWords(char[] a, int n)` and `char[] cleanSpaces(char[] a, int n)` as well as `void reverse(char[] a, int i, int j)` **all utilizes two pointers technique** to remove spaces and reverse string. ## Solution Adapted Version - Two Pointers + multi-reversal: O(n) time, O(1) space (6ms) ```java public class Solution { public String reverseWords(String s) { if (s == null) return null; char[] c = s.toCharArray(); int m = c.length; // step 1. clean up spaces char[] a = cleanSpaces(c, m); int n = a.length; // step 2. reverse the whole string reverse(a, 0, n - 1); // step 3. reverse each word reverseWords(a, n); return new String(a); } void reverseWords(char[] a, int n) { int i = 0, j = 0; while (i < n) { while (i < n && a[i] == ' ') { i++; // skip spaces } // i is now the first index in the non-space word // update right pointer j = i; while (j < n && a[j] != ' ') { j++; // skip non-spaces } // j is now the first space on the right of a word // reverse the word we just found reverse(a, i, j - 1); // update left pointer i = j; } } // trim leading, trailing and multiple spaces char[] cleanSpaces(char[] a, int n) { int i = 0, j = 0; while (i < n && j < n) { while (j < n && a[j] == ' ') { j++; // skip spaces } while (j < n && a[j] != ' ') { a[i++] = a[j++]; // copy non-spaces } while (j < n && a[j] == ' ') { j++; // skip spaces } if (j < n) { a[i++] = ' '; // append only one space } } return Arrays.copyOf(a, i); } // reverse a[] from a[i] to a[j] private void reverse(char[] a, int i, int j) { while (i < j) { char t = a[i]; a[i++] = a[j]; a[j--] = t; } } } ``` Multi-reverse + Two Pointers - O(n) time, O(1) space (7ms) [https://leetcode.com/problems/reverse-words-in-a-string/discuss/47720/Clean-Java-two-pointers-solution-(no-trim(-)-no-split(-)-no-StringBuilder\\](https://leetcode.com/problems/reverse-words-in-a-string/discuss/47720/Clean-Java-two-pointers-solution-%28no-trim%28-%29-no-split%28-%29-no-StringBuilder%29\\) ```java public class Solution { public String reverseWords(String s) { if (s == null) return null; char[] a = s.toCharArray(); int n = a.length; // step 1. reverse the whole string reverse(a, 0, n - 1); // step 2. reverse each word reverseWords(a, n); // step 3. clean up spaces return cleanSpaces(a, n); } void reverseWords(char[] a, int n) { int i = 0, j = 0; while (i < n) { while (i < n && a[i] == ' ') { i++; // skip spaces } // i is now the first index in the non-space word // update right pointer j = i; while (j < n && a[j] != ' ') { j++; // skip non-spaces } // j is now the first space on the right of a word // reverse the word we just found reverse(a, i, j - 1); // update left pointer i = j; } } // trim leading, trailing and multiple spaces String cleanSpaces(char[] a, int n) { int i = 0, j = 0; while (j < n) { while (j < n && a[j] == ' ') j++; // skip spaces while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces while (j < n && a[j] == ' ') j++; // skip spaces if (j < n) a[i++] = ' '; // keep only one space } return new String(a).substring(0, i); } // reverse a[] from a[i] to a[j] private void reverse(char[] a, int i, int j) { while (i < j) { char t = a[i]; a[i++] = a[j]; a[j--] = t; } } } ``` Using String operations `trim()`, `split()`- (65ms AC) ```java public class Solution { public String reverseWords(String s) { String[] parts = s.trim().split("\\s+"); String out = ""; for (int i = parts.length - 1; i > 0; i--) { out += parts[i] + " "; } return out + parts[0]; } } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://aaronice.gitbook.io/lintcode/string/reverse-words-in-a-string.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.