翻转字符串

题意

给定一个字符串,逐个翻转字符串中的每个单词。

  • 单词的构成:无空格字母构成一个单词
  • 输入字符串是否包括前导或者尾随空格?可以包括,但是反转后的字符不能包括
  • 如何处理两个单词间的多个空格?在反转字符串中间空格减少到只含一个

样例

传入一个字符串 " Hello World! ",返回 "World! Hello"

思路

  1. 首先 目标字符串null 或者长度为 0,则直接返回空字符串;
  2. 先去除两端的空格之后,再找到 目标字符串 的第一个空格的位置
  3. 然后用 subString() 将第一个空格之前的子字符串压入栈中
  4. 将目标字符串剩下的另一半子字符串继续进行第二步操作,直至 目标字符串 的长度变为0
  5. 将栈中的所有元素以此出栈,除最后一个元素外,其他元素尾部都加上一个空格: " "

注意当目标字符串没有空格时,取第一个空格的位置会返回 -1 ,此时用这个位置去取字符串会出现下标越界!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
/**
* @param s : A string
* @return : A string
*/
public String reverseWords(String s) {

if (s == null || s.length() == 0) {
return "";
}

Stack<String> stack = new Stack<String>();

while (s.length() != 0) {
s = s.trim();
int i = s.indexOf(" ");

if ( i== -1) {
stack.push(s);
break;
}

stack.push( s.substring(0, i) );
s = s.substring(i, s.length());

}

String str = "";

while (!stack.isEmpty()) {
if(stack.size()==1)
str = str + stack.pop();
else
str = str + stack.pop() + " ";
}

return str;
}
}

原题地址

LintCode:翻转字符串