Reverse Words in a String III
EasyPrompt
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"Example 2:
Input: s = "Mr Ding"
Output: "rM gniD"
Constraints:
1 <= s.length <= 5 * 104scontains printable ASCII characters.sdoes not contain any leading or trailing spaces.- There is at least one word in
s. - All the words in
sare separated by a single space.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is straightforward and relies on built-in language features. The idea is to first break the sentence down into its constituent words, handle each word individually, and then piece the sentence back together.
Algorithm
- Split the input string
sby the space character (' ') to create an array of strings, where each element is a word. - Initialize an empty
StringBuildercalledresultto build the output string. - Iterate through the
wordsarray. - For each
word, create a newStringBuilderfrom it, call thereverse()method, and append the reversed word to theresult. - After appending a reversed word, check if it's not the last word in the array. If it's not, append a space to the
resultto maintain the separation between words. - After the loop completes, convert the
resultStringBuilderto a string and return it.
Walkthrough
In this method, we first use the split() function to divide the input string s into an array of words, using the space character as a delimiter. This gives us a clean list of all the words.
Next, we iterate over this array. For each word, we can use a StringBuilder to easily reverse the characters. We create a StringBuilder with the current word, call its reverse() method, and then append this reversed word to a main StringBuilder that will hold our final result.
To preserve the original sentence structure, we also append a space after each reversed word, except for the very last one. Finally, we convert the main StringBuilder back to a string to get our desired output.
class Solution { public String reverseWords(String s) { String[] words = s.split(" "); StringBuilder result = new StringBuilder(); for (int i = 0; i < words.length; i++) { String word = words[i]; StringBuilder reversedWord = new StringBuilder(word); reversedWord.reverse(); result.append(reversedWord); if (i < words.length - 1) { result.append(" "); } } return result.toString(); }}Complexity
Time
O(N), where N is the length of the input string. The `split()` operation takes O(N) time. Reversing each word and building the new string also takes O(N) time in total, as each character is processed a constant number of times.
Space
O(N), where N is the length of the input string. This space is used to store the array of words created by `split()` and the `StringBuilder` for the result. In the worst case, the array of words can take up O(N) space.
Trade-offs
Pros
Simple to implement and easy to understand due to the high-level abstractions used.
Code is often more concise and readable.
Cons
Creates several intermediate data structures, such as an array of strings for the words and a new
StringBuilderfor each word, leading to higher memory consumption.The overhead of splitting the string and creating multiple new objects can be less performant than in-place manipulation, especially for very long strings.
This is a more optimized approach that modifies a character array representation of the string in-place. It avoids the overhead of creating an array of separate string objects, making it more efficient in terms of memory and speed.
Algorithm
- Convert the input string
sinto a character arraycharsto allow for in-place modification. - Initialize a pointer
start = 0to mark the beginning of the current word. - Iterate through the
charsarray with a pointerendfrom0tos.length(). - When
chars[end]is a space orendreaches the end of the string, we have found a word boundary. The word is located from indexstarttoend - 1. - Call a helper function to reverse the characters in the
charsarray between thestartandend - 1indices. - After reversing, update
starttoend + 1to set the beginning of the next word. - Once the loop is complete, convert the modified
charsarray back into a string and return it.
Walkthrough
Instead of splitting the string into an array of words, this method works on a single mutable sequence of characters. First, we convert the input string into a character array.
We then use two pointers to walk through this array. A start pointer keeps track of the beginning of the current word, and an end pointer scans forward to find the end of that word. A word ends when we encounter a space or reach the end of the entire string.
Once a word is identified (from start to end - 1), we call a helper function to reverse that specific segment of the character array. This reversal is done in-place, by swapping characters from the outer edges of the word towards the center. After a word is reversed, we update the start pointer to the position right after the space, and the process continues for the next word.
After iterating through the entire array, all words will have been reversed in place. The final step is to convert the modified character array back into a string.
class Solution { public String reverseWords(String s) { char[] chars = s.toCharArray(); int start = 0; for (int end = 0; end <= chars.length; end++) { if (end == chars.length || chars[end] == ' ') { // Found a word from start to end - 1 reverse(chars, start, end - 1); // Move start to the beginning of the next word start = end + 1; } } return new String(chars); } private void reverse(char[] arr, int left, int right) { while (left < right) { char temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } }}Complexity
Time
O(N), where N is the length of the string. We iterate through the character array once to find the words, and the reversal process ensures that each character is swapped at most once. Therefore, each character is touched a constant number of times.
Space
O(N), where N is the length of the string. In Java, strings are immutable, so a character array of size N is required to perform the modifications. This is the auxiliary space needed.
Trade-offs
Pros
More efficient in terms of memory as it avoids creating an intermediate array of strings.
Generally faster as it reduces object creation overhead and relies on direct array manipulation.
Cons
The logic is slightly more complex than the split-and-join method, requiring manual tracking of word boundaries.
Requires a helper function for the in-place reversal, which adds a bit more code.
Solutions
Solution
class Solution {public String reverseWords(String s) { StringBuilder res = new StringBuilder(); for (String t : s.split(" ")) { for (int i = t.length() - 1; i >= 0; --i) { res.append(t.charAt(i)); } res.append(" "); } return res.substring(0, res.length() - 1); }}/** * @param {string} s * @return {string} */ var reverseWords = function (s) { return s .split(" ") .map((t) => t.split("").reverse().join("")) .join(" ");};class Solution {public: string reverseWords(string s) { for (int i = 0, n = s.size(); i < n; ++i) { int j = i; while (++j < n && s[j] != ' ') ; reverse(s.begin() + i, s.begin() + j); i = j; } return s; }};class Solution : def reverseWords ( self , s : str ) -> str : return ' ' . join ([ t [:: - 1 ] for t in s . split ( ' ' )])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.