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 * 104s contains printable ASCII characters.s does not contain any leading or trailing spaces.s.s are separated by a single space.The key idea in Reverse Words in a String III is to reverse the characters of each individual word while keeping the original word order intact. A common and efficient strategy is to iterate through the string and detect word boundaries separated by spaces. Once a word is identified, you can reverse its characters before moving to the next word.
An effective approach uses the two pointers technique. Maintain a start pointer at the beginning of a word and move an end pointer until a space or the end of the string is reached. The characters between these pointers can then be reversed using a simple swapping process. This can be done either by converting the string into a char[] for in-place manipulation or by reversing substrings and rebuilding the result.
This approach ensures that each character is processed only once, making it highly efficient. Because operations are localized within each word, the algorithm remains straightforward while maintaining optimal performance.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers with In-place Character Reversal | O(n) | O(1) or O(n) depending on implementation |
Knowledge Center
This approach involves splitting the given string into words, reversing each word individually, and then joining them back together.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as only a constant amount of extra space is used.
1public class Solution {
2 public static void reverseWords(String s) {
3 char[] arr = s.toCharArray();
4 int n = arr.length;
5 int start = 0;
6
7 for (int end = 0; end < n; end++) {
8 if (arr[end] == ' ' || end == n - 1) {
9 reverse(arr, start, (end == n - 1) ? end : end - 1);
10 start = end + 1;
11 }
12 }
13 System.out.println(new String(arr));
14 }
15
16 private static void reverse(char[] arr, int start, int end) {
17 while (start < end) {
18 char temp = arr[start];
19 arr[start] = arr[end];
20 arr[end] = temp;
21 start++;
22 end--;
23 }
24 }
25
26 public static void main(String[] args) {
27 String s = "Let's take LeetCode contest";
28 reverseWords(s);
29 }
30}This Java solution uses a similar approach to the C solution. It reverses each word in place using a helper function.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, string manipulation problems like this are common in coding interviews at FAANG and other tech companies. They test understanding of two pointers, string traversal, and efficient in-place operations.
A character array is often the best choice because it allows in-place swapping while reversing each word. This reduces extra memory usage and keeps the algorithm efficient.
The optimal approach uses the two pointers technique to identify each word and reverse its characters. By scanning the string once and reversing characters within word boundaries, the problem can be solved efficiently in linear time.
Yes, if the string is converted to a mutable character array, you can reverse each word directly using swaps. This allows the solution to run with constant extra space aside from the input storage.
JavaScript implementation leverages array destructuring to reverse characters in place. The two-pointer strategy helps locate word boundaries efficiently.