151. Reverse Words in a String.md

151. Reverse Words in a String

Problem

Given an input string, reverse the string word by word.

For example, Given s = "the sky is blue", return "blue is sky the".

tag:

• string
• StringBuffer, StringBuilder, String

Solution

一种简单的方法是两边遍历， 第一遍遍历分离出字符串中的word， 保存在数组中， 第二遍遍历对字符串反转

从后向前迭代可以做到一次遍历， 纪录每个单词的起始位置，append到反转字符串

时间复杂度O(n)， 空间负载都O（n)

java

	public String reverseWords(String s) {
		StringBuilder reversed = new StringBuilder();
		int j = s.length();
		for (int i = s.length() - 1; i >= 0; i--) {
			if (s.charAt(i) == ' ') {
				j = i;
			} else if (i == 0 || s.charAt(i - 1) == ' ') {
				if (reversed.length() != 0) {
					reversed.append(' ');
				}
				reversed.append(s.substring(i, j));
			}
		}
		return reversed.toString();
	}

go