# Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

``````Input:
"Let's take LeetCode contest"

Output:
"s'teL ekat edoCteeL tsetnoc"``````

Note:In the string, each word is separated by single space and there will not be any extra space in the string.

## Analysis

O(n) time - 嵌套循环时每个元素最多遍历三次（一次右指针，一次左指针，还有一次是swap/reverse时）

O(n) space - 用了辅助以及存结果用的char array

## Solution

Two Pointers - Reverse - O(n) time, O(n) space - (8ms)

``````class Solution {
public String reverseWords(String s) {
int i = 0, j = 0;
int n = s.length();
char[] chs = s.toCharArray();
while (i < n && j < n) {
while (i < n && chs[i] == ' ') {
i++;
}
j = i;
while (j < n && chs[j] != ' ') {
j++;
}
reverse(chs, i, j - 1);
i = j;
}
return new String(chs);
}

private void reverse(char[] chs, int s, int t) {
while (s < t) {
char tmp = chs[s];
chs[s] = chs[t];
chs[t] = tmp;
s++;
t--;
}
}
}``````

``````    public String reverseWords(String s) {
String[] str = s.split(" ");
for (int i = 0; i < str.length; i++) str[i] = new StringBuilder(str[i]).reverse().toString();
StringBuilder result = new StringBuilder();
for (String st : str) result.append(st + " ");
return result.toString().trim();
}``````

Last updated