剑指Offer_#58 - I. 翻转单词顺序
Contents
题目
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
思路分析
分为两步
- 第一步是分词，即把用空格来做分隔符的单词全都提取出来。分词这一步有两个方法。
- 使用
split()方法分词。需要注意的是，如果两个单词之间有多个空格，分词结果当中会出现空字符串"",拼接时遇到空字符串需要跳过。 - 如果面试官要求不能使用
split()方法，可以使用双指针从后向前遍历分词。左指针和右指针分别指向一个单词的开头和结尾。
- 使用
- 第二步是构造结果字符串，按照从后往前的顺序重新拼接出所需的翻转字符串。
- 使用
StringBuilder对象，将分词结果按照从后向前的顺序重新拼接起来。
- 使用
解答
解答1：split()分词
class Solution {
public String reverseWords(String s) {
//以空格作为分隔符，分词
String[] strArray = s.trim().split(" ");
StringBuilder res = new StringBuilder();
for(int i = strArray.length - 1;i >= 0;i--){
//连续空格在分词时，结果会包含空字符串
if(strArray[i].equals("")) continue;
//最后会多出一个空格，返回前用trim()处理即可
res.append(strArray[i] + " ");
}
return res.toString().trim();
}
}复杂度分析
时间复杂度:O(n)，需要参考trim()和split()函数的复杂度，这两个函数的复杂度都是O(n),可以参考What's the complexity of Java's string split function?
空间复杂度：O(n),分词后的字符串数组str占用空间为O(n)，StringBuilder对象占用空间为O(n)
解答2：双指针遍历分词（从后向前）
class Solution {
public String reverseWords(String s) {
String str = s.trim();
int j = str.length() - 1;//单词的右边界
StringBuilder res = new StringBuilder();
int i = j;//单词左边界
//ERROR:如果没有等号，那么第一个单词只有一个字符时，就无法通过
while(i >= 0){
//跳过最后一个单词
while(i >= 0 && str.charAt(i) != ' ') i--;
res.append(str.substring(i + 1,j + 1) + " ");
//跳过单词中间的空格
while(i >= 0 && str.charAt(i) == ' ') i--;
j = i;
}
return res.toString().trim();
}
}复杂度分析
时间复杂度：O(n),线性遍历一次
空间复杂度：O(n),StringBuilder对象占用空间为O(n)