题目描述
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
提示：
在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
数据结构
- 字符串、字符数组
算法思维
- 遍历、逆序、双指针
解题要点
- 如何优化实现一个单词中的字符反转
解题思路
一. Comprehend 理解题意
- 单词的顺序不变
- 颠倒每个单词内部字符的顺序
二. Choose 选择数据结构与算法
双指针 解法
- 数据结构：指针、字符串
- 算法思维：遍历、逆序、双指针
解题思路
- 声明双指针和缓存
- 遍历字符串
如果不是：读到了字符串末尾 或者 读到了空格
判断首指针是否为空
如果为空就赋值成当前位置
不管首指针是否为空，尾指针都和遍历位置对齐
如果：读到了末尾，或者读到了空格
判断首指针是否为空
如果不为空，就逆序遍历首尾指针之间的所有字符，存入缓冲区
每读完一个单词都要添加一个空格，并且将首尾指针复原 - 最终去掉缓冲区末尾的空格后，作为字符串返回
边界问题
- 为了讨论最后一个字符非空的情况，将边界条件设为：
i <= s.length()
细节问题
- 需要非空判断
- 遍历完整个字符串，需要判断当前首尾指针中间是都有数据
如果有数据，要额外写入一次到缓存区中，避免丢失最后一个单词
三. Code 编码实现基本解法
class Solution {
public String reverseWords(String s) {
int len = s.length();
//0.非空判断
if (len == 0) return "";
//1.声明双指针和缓存
int first = -1, last = -1;
StringBuffer sb = new StringBuffer();
char[] arr = s.toCharArray();
//2.遍历字符串
for (int i = 0; i <= len; i++) {
//3.如果不是读到了字符串末尾，或者读到了空格
if (i != len && arr[i] != ' ') {
//4.就判断首指针是否为空，如果为空就赋值成当前位置
if (first == -1) {
first = i;
}
//5.不管首指针是否为空，尾指针都和遍历位置对齐
last = i;
} else if (first != -1) { //6.如果读到了末尾，或者读到了空格，且首指针不为空
//7.逆序遍历首尾指针之间的所有字符，存入缓冲区
while (last >= first) {
sb.append(arr[last]);
last--;
}
//8.每读完一个单词都要添加一个空格，并且将首尾指针复原
sb.append(' ');
first = -1;
last = -1;
}
}
//9.最终去掉缓冲区末尾的空格后，作为字符串返回
return sb.substring(0,sb.length()-1);
}
}
执行耗时：8 ms，击败了 56.64% 的Java用户
内存消耗：39 MB，击败了 64.81% 的Java用户
时间复杂度：O(n) -- 两次字符串的遍历 O(n)
空间复杂度：O(n) -- 一个缓冲区 O(n)，两个指针 O(1)
四. Consider 思考更优解
改变算法思维
- 使用遍历的方式反转字符效率太低
- 使用 StringBuffer 作为缓冲区存取数据，消耗时间和空间
- 题目给定了条件：“每个单词由单个空格分隔”
因此可以使用 双指针 + 字符数组 的方式直接 原地反转 字符
五. Code 编码实现最优解
优化解法：原地反转
class solution{
//使用双指针，原地反转单词
public String reverseWords(String s) {
if (s == null || s.length() == 0) {//边界检查
return s;
}
char[] chars = s.toCharArray();
int len = chars.length;
//指向单词的初始字符
int start = 0;
int end = 0;//指向单词的结尾字符或者是终止索引
//截取单词进行 单词翻转
for (int i = 0; i < len; i++) {
if (chars[i] == ' ') {//如果查询到了空格，一个单词结束
end = i - 1;
reverse(chars, start, end);
start = i + 1;//反转单词之后把start指向下一个单词的起始
} else if (i == len - 1) {//如果查询到了数组最后一个字符，一个单词结束
reverse(chars, start, len - 1);
}
}
return new String(chars);
}
//双指针原地翻转方法，给定反转的源数组，给定起始索引和终止索引
public void reverse(char[] s, int start, int end) {
while (start < end) {//如果起始索引小于终止索引，进行反转
//交换双指针对应的字符
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
}
执行耗时：3 ms，击败了 99.88% 的Java用户
内存消耗：39.2 MB，击败了 34.70% 的Java用户
时间复杂度：O(n) -- 字符串的遍历 O(n)
空间复杂度：O(1) -- 字符数组 O(1)，双指针 O(1)
六. Change 变形与延伸
=== 待续 ===
