LeetCode 186: Reverse Words in a String II
Problem Description
Explanation:
Given a character array s, reverse the order of characters in each word within the array while still preserving whitespace and initial word order.
Algorithm:
- Reverse the entire character array
s. - Iterate through the reversed array and for each word, reverse the characters to get the original word order.
- Finally, reverse the entire array again to get the correct order of words with reversed characters.
Time Complexity: O(n), where n is the length of the character array s.
Space Complexity: O(1)
:
Solutions
class Solution {
public void reverseWords(char[] s) {
reverse(s, 0, s.length - 1);
int start = 0;
for (int end = 0; end < s.length; end++) {
if (s[end] == ' ') {
reverse(s, start, end - 1);
start = end + 1;
}
}
reverse(s, start, s.length - 1);
}
private void reverse(char[] s, int left, int right) {
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}Related LeetCode Problems
Loading editor...