双指针
解题思路
倒序遍历字符串 s ，记录单词左右索引边界 i、j；
每确定一个单词的边界，则将其添加至单词列表 res；
最终将单词列表拼接为字符串，并返回即可；
复杂度
-
时间复杂度：
O(N)，其中 N 为字符串 s 的长度，线性遍历字符串； -
空间复杂度：
O(N)；
代码实现
var reverseWords = function (s) {
let res = '';
s = s.trim(); // 删除首尾空格
let j = s.length - 1, i = j;
while (i >= 0) {
while (i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
res += (s.substring(i + 1, j + 1) + " "); // 添加单词
while (i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.trim();
};
字符串
解题思路
先去掉字符串两端的空格；
沿着字符串一个一个单词处理；
然后将单词压入队列的头部，再将队列转成字符串即可；
复杂度
-
时间复杂度：
O(n)，其中 n 为输入字符串的长度； -
空间复杂度：
O(n)，双端队列存储单词需要O(n)的空间；
代码实现
var reverseWords = function (s) {
// 左右指针
let left = 0;
let right = s.length - 1;
// 左进右出的队列
let queue = [];
// 临时的 word，当单词是完整的时候放入队列中
let word = '';
// 去掉左右两侧的空格
while (s.charAt(left) === ' ') left++;
while (s.charAt(right) === ' ') right--;
// 迭代
while (left <= right) {
let ch = s.charAt(left);
if (ch == ' ' && word) {
// 如果 ch 是空格，word 是一个单词，则把单词放入队列，并清空 word
queue.unshift(word);
word = '';
} else if (ch !== ' ') {
// 如果 ch 不是空格，说明这个单词还没有拼装完整
word += ch;
}
left++;
}
// 由于两侧的空格已经被去掉了，最后一个单词不能进入 if 代码块中，则手动将 word 放入队列中
queue.unshift(word);
return queue.join(' ');
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 438. 找到字符串中所有字母异位词
上一篇
评论
