LeetCode刷题实战186:翻转字符串里的单词 II
Given an input string , reverse the string word by word.
Example:
Input: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
题意
示例
示例:
输入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
注意:
单词的定义是不包含空格的一系列字符
输入字符串中不会包含前置或尾随的空格
单词与单词之间永远是以单个空格隔开的
进阶:使用 O(1) 额外空间复杂度的原地解法。
解题
class Solution {
public void reverseWords(char[] str) {
int i = 0;
for (int j = 0; j < str.length; j++) { // aTbTc
if (str[j] == ' ') {
reverse(str, i, j);
i = j + 1;
}
}
reverse(str, i, str.length); // 最后一个单词末尾没有空格
System.out.println(String.valueOf(str));
reverse(str, 0, str.length); // 整体再翻转一次
}
/**
* 将 str 的 [i, j] 进行翻转,如 "the" 转换后变成 “eht”
* 注意,[i,j] 是左闭右开
*
* @param str
* @param i
* @param j
*/
private void reverse(char[] str, int i, int j) {
for (int k = i; k < (i + j) / 2; k++) {
char tmp = str[k]; // 位置 k 的元素
int g = j - 1 - k + i; // 位置 k 的对称位置
str[k] = str[g];
str[g] = tmp;
}
}
}
评论