LeetCode 186 - Reverse Words in a String II

作者 QIFAN 日期 2017-02-10
LeetCode 186 - Reverse Words in a String II

原题链接: 186. Reverse Words in a String II


题干

给定一个 String 含有多个单词,返回单词倒序的 string 。

要求 in-place

思路

很聪明的一个解法。先 reverse 整个数组,再分别把单词 reverse 。时间复杂度 $O(n)$ 。

代码:

public void reverseWords(char[] s) {
if (s == null || s.length <= 1) {
return;
}
reverse(s, 0, s.length - 1);
int index = 0;
int wordStart = 0;
while (index < s.length) {
while (index < s.length && s[index] != ' ') {
index++;
}
reverse(s, wordStart, index - 1);
index++;
wordStart = index;
}
}
private void reverse(char[] s, int lo, int hi) {
while (lo < hi) {
char temp = s[hi];
s[hi] = s[lo];
s[lo] = temp;
lo++;
hi--;
}
}