LeetCode 557 Reverse Words in a String III

LeetCode 557 Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note:In the string, each word is separated by single space and there will not be any extra space in the string.

题目大意：

给定字符串，将每个单词逐字符逆置，返回新字符串。注意：字符串中单词之间有且只有1个空格分开。

解题思路：

这里考到StringBuilder，对于字符串连接效率高。还有一个小技巧，就是往输入参数附加一个空格，这样for循环结束后不用特别处理边界情况。
第一种方法是以单词为扫描单位，把字符串分成单词字符串数组，然后把每个单词反转及一个空格加入到结果sb中。
第二种方法是以字符为扫描单位，遇到空格是，就把之前存入的word放入sb中，再进行下一轮word扫描。

注意事项：

用StringBuilder
末尾加入空格

Java代码：

第一种方法

public String reverseWords(String s) {
	String[] tokens = s.split(" ");
	StringBuilder sb = new StringBuilder();
	for(String token : tokens)
		sb.append(new StringBuilder(token).reverse().toString()+" ");
	
	return sb.toString().trim();
}

第二种方法

public String reverseWords(String s) {
	s = s+" ";
	StringBuilder sb = new StringBuilder();
	StringBuilder word = new StringBuilder();
	for(char c : s.toCharArray()){
		if(c!=' ')
			word.append(c);
		else
		{
			sb.append(word.reverse().toString()+" ");
			word = new StringBuilder();
		}
	}
	return sb.toString().trim();
}

算法分析：

两种方法时间复杂度为O(n)，n为字符串长度。第一种方法空间复杂度为O(n)，而第二种方法为O(1)。