Sponsored
Sponsored
This approach involves splitting the original string into individual words using space as a delimiter, reversing the list of words, and then joining them back together with a single space.
Time Complexity: O(N), where N is the length of the string, as we process each character once.
Space Complexity: O(N), additional space for intermediate and result storage.
1
The Java solution uses split() with a regular expression to tokenize the input string by spaces while eliminating leading/trailing/multiple spaces. The words are stored in a reverse manner using a StringBuilder for the final output.
This optimized approach manipulates the string in place by using a character array. We'll first reverse the entire string, and then reverse each word to return them to their correct order.
Time Complexity: O(N), where N is the number of characters in the string.
Space Complexity: O(1), as the operation is done in-place without extra space.
1using System;
2using System.Text;
3
4public class Solution {
5 public static string ReverseWords(string s) {
6 char[] chars = s.Trim().ToCharArray();
7 int n = chars.Length;
8
9 void Reverse(int start, int end) {
10 while (start < end) {
11 char temp = chars[start];
12 chars[start] = chars[end];
13 chars[end] = temp;
14 start++;
15 end--;
16 }
17 }
18
19 Reverse(0, n - 1);
20
21 int rightIndex = 0;
22 for (int i = 0; i < n; ++i) {
23 if (chars[i] == ' ') continue;
24 int start = i;
25 while (i < n && chars[i] != ' ') i++;
26 Reverse(start, i - 1);
27 while (start < i) chars[rightIndex++] = chars[start++];
28 if (rightIndex < n) chars[rightIndex++] = ' ';
29 }
30
31 return new String(chars, 0, rightIndex == 0 ? 0 : rightIndex - 1);
32 }
33
34 public static void Main() {
35 string input = " hello world ";
36 string output = ReverseWords(input);
37 Console.WriteLine(output);
38 }
39}The C# solution includes reversing the whole character array initially, and then processing each token to be reversed in place before constructing the final string with correct whitespace handling.
Solve with full IDE support and test cases