151. 翻转字符串里的单词
2020-08-28 本文已影响0人
一角钱技术
151. 翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶：
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。
方法1：使用语言特性
算法思路：
很多语言对字符串提供了 split（拆分），reverse（翻转）和 join（连接）等方法，因此我们可以简单的调用内置的 API 完成操作：
- 使用 split 将字符串按空格分割成字符串数组；
- 使用 reverse 将字符串数组进行反转；
- 使用 join 方法将字符串数组拼成一个字符串。
参考代码：
class Solution {
public String reverseWords(String s) {
// 正则匹配连续的空白字符作为分隔符分割 \\s+
String[] words = s.trim().split(" +");
Collections.reverse(Arrays.asList(words));
return String.join(" ", words);
}
}
复杂度分析：
-
时间复杂度：O(N)，其中 N 为输入字符串的长度。
-
空间复杂度：O(N)，用来存储字符串分割之后的结果。
方法2：先翻转整个字符串，再逐个翻转单词.
算法思路：
- 整体思路：先翻转整个字符串，再逐个翻转单词。
- 在“逐个翻转单词”时
对于一个位置i， 如果s[i]==' '而s[i-1]!=' ', 则i-1可视作一个单词的“末尾位置”， i位置的空格应被保留， 其余的空格被视为“多余空格”.
第1个单词的“开始位置”为0， 但从该位置开始往后的一段范围内可能全是空格，这些空格被视作“多余空格”，则 i++ ；
第1个单词的“末尾位置”，从 i 开始，即 j = i，从该位置开始往后找到不是空格的位置，即该单词末尾位置， j++ 。
在对第k个单词进行翻转后，一些多余空格（如果有）跑到了第k个单词后部。
- 在对所有单词进行翻转后
所有多余空格都集中在字符串末尾，进行清除空格操作。
参考代码2:
class Solution {
public String reverseWords1(String s) {
if (s == null || s.length() == 0) {
return s;
}
char[] chars = s.toCharArray();
int n = s.length();
// 翻转整个数组
reverse(chars, 0, n - 1);
// 翻转每个单词
vord_reverse(chars, n);
// 去除多余的空格
return clean_space(chars, n);
}
private void reverse(char[] chars, int start, int end) {
while (start < end) {
char temp = chars[start];
chars[start++] = chars[end];
chars[end--] = temp;
}
}
private void vord_reverse(char[] chars, int n) {
int i = 0, j = 0;
while (j < n) {
// 找到第一个首字母
while (i < n && chars[i] == ' ') {
i++;
}
j = i;
// 末位置
while (j < n && chars[j] != ' ') {
j++;
}
reverse(chars, i, j - 1);
i = j;
}
}
private String clean_space(char[] chars, int n) {
int i = 0, j = 0;
while (j < n) {
while (j < n && chars[j] == ' ') j++;
while (j < n && chars[j] != ' ') chars[i++] = chars[j++];
while (j < n && chars[j] == ' ') j++;
if (j < n) chars[i++] = ' ';
}
return new String(chars).substring(0, i);
}
}
方法3：双端队列
算法思路：
由于双端队列支持从队列头部插入的方法，因此我们可以沿着字符串一个一个单词处理，然后将单词压入队列的头部，再将队列转成字符串即可。
参考代码3:
class Solution {
public String reverseWords(String s) {
int left = 0, right = s.length() - 1;
// 去掉字符串开头的空白字符
while (left <= right && s.charAt(left) == ' ') ++left;
// 去掉字符串末尾的空白字符
while (left <= right && s.charAt(right) == ' ') --right;
Deque<String> d = new ArrayDeque();
StringBuilder word = new StringBuilder();
while (left <= right) {
char c = s.charAt(left);
if ((word.length() != 0) && (c == ' ')) {
// 将单词 push 到队列的头部
d.offerFirst(word.toString());
word.setLength(0);
} else if (c != ' ') {
word.append(c);
}
++left;
}
d.offerFirst(word.toString());
return String.join(" ", d);
}
}
复杂度分析：
- 时间复杂度：O(N)，其中 N 为输入字符串的长度。
- 空间复杂度：O(N)，双端队列存储单词需要 O(N) 的空间。
部分图片来源于网络，版权归原作者，侵删。
以上谢谢大家，求赞求赞求赞！
