151. Reverse Words in a String
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue" **Output: **"blue is sky the"
Example 2:
Input: " hello world! " **Output: **"world! hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: "a good example" **Output: **"example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Note:
- A word is defined as a sequence of non-space characters.
- Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
- You need to reduce multiple spaces between two words to a single space in the reversed string.
思路：
核心思路就是找到两个空格之间的单词，然后生成这个新单词。正则表达式消耗了一些时间，用递归之后运行时间降低了不少。
代码：
java：
代码语言：javascript复制class Solution {
/*public String reverseWords(String s) {
if (s == null || s.length() == 0) return "";
StringBuilder sb = new StringBuilder();
String[] words = s.trim().split("\s ");
for (int i = words.length - 1; i >= 0; i--)
sb.append(words[i] " ");
return sb.toString().trim();
}*/
// 递归
public String reverseWords(String s) {
return reverse(0,s).toString();
}
private StringBuilder reverse(int index, String s) {
// 1.找到第一个非空格.
while (index < s.length() && s.charAt(index) == ' ') index ;
// 2.后面全是空格，就返回一个空对象
if(index == s.length()) return new StringBuilder();
// 3.找到下一个空格.
int start = index;
index = s.indexOf(' ', start);
// 4.后面没有空格，就返回后面的字符串
if (index == -1) return new StringBuilder(s.substring(start));
// 5.后面还有空格，就继续递归
调用
StringBuilder remainStr = reverse(index 1, s);
// 根据返回的sb对象，返回给上一层调用
return remainStr.length() == 0 ?
// 如果StirngBuilder长度为0，就说明后面全是空格，直接返回这一层调用的这个word
new StringBuilder(s.substring(start, index)):
// 如果StringBuilder长度不为零，就说明后面要么是原字符串最后一个单词，要么是下层调用返回的StringBuilder，
// 就加空格再加上本层调用的单词，然后继续返回给上层。
remainStr.append(" ").append(s.substring(start, index));
}
}
