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.
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); }}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.