rainyzz's blog

Reverse Words in a String

###Reverse Words in a String https://oj.leetcode.com/problems/reverse-words-in-a-string/
Given an input string, reverse the string word by word.
For example, Given s = “the sky is blue”, return “blue is sky the”.

刚开始的想法就是用Java的split函数来把词分到数组里,然后反向加一下,刚开始是这么写的

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public String reverseWords(String s) {
String result = "";
String[] words = s.trim().split(" ");
String space = "";
for(int i = words.length - 1; i >= 0; i--){
result += space;
result +=words[i];
space = " ";
}
return result;
}
}

后来发现题目还会有多个空格,split函数你传给它一个空格它就只按一个空格来分割,不像python等语言如果你默认不给参数就会按照空白来分,包括多个空格,制表符等。

经过查资料还知道split函数的参数其实是正则表达式,这样就能用正则来识别多个空格了,然后我将\\s+传给split函数来匹配任意空格,然后一提交,发现超时了,系统返回的信息提示上次处理的数据的长度竟然有50000。

然后我将split的参数改成[ ]+,只匹配多个空格,还是超时。接下来要想提速,就在正则表达式和字符串拼接这两部分。我先试了字符串拼接,用StringBuffer而不是String的+=来拼接,然后就顺利通过了,代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public String reverseWords(String s) {
String[] words = s.trim().split("[ ]+");
String space = "";
StringBuffer sb = new StringBuffer();
for(int i = words.length - 1; i >= 0; i--){
sb.append(space);
sb.append(words[i]);
space = " ";
}
return sb.toString();
}
}

看来以后用字符串拼接还是用StringBuffer好,省时间太多了,因为String的+=拼接会一直创建新的String对象,StringBuffer就不需要重新创建对象。在这篇文章http://blog.csdn.net/yirentianran/article/details/2871417,作者拼接了26个英文字母5000次,速度差别达到了上万倍。

还有一个StringBuilder,StringBuilder与StringBuffer的区别就是StringBuffer是线程安全的,StringBuilder是线程不安全的。