leetcode面试准备:Reverse Words in a String

1 题目

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

For example,

Given s = "the sky is blue",

return "blue is sky the".

Update (2015-02-12):

For C programmers: Try to solve it in-place in O(1) space.

2 思路

介绍一种很直接的做法，就是类似于java中String::split函数做的操作，把字符串按空格分开，不过我们把重复的空格直接忽略过去。接下来就是把得到的结果单词反转过来得到结果。因为过程中就是一次扫描得到字符串，然后再一次扫描得出结果，所以时间复杂度是O(n)。空间上要用一个数组来存，所以是O(n)。

use split() method,clean up redundancy like "",and then reverse the words.
advanced point:regular expression "\\s+" can clean up redundancy blank.
attention:if input is " ", the expect output is "". and the code is ok because of split("\s+").

再介绍另一种方法，思路是先把整个串反转并且同时去掉多余的空格，然后再对反转后的字符串对其中的每个单词进行反转，比如"the sky is blue"，先反转成"eulb si yks eht"，然后在对每一个单词反转，得到"blue is sky the"。这种方法先反转的时间复杂度是O(n)，然后再对每个单词反转需要扫描两次（一次是得到单词长度，一次反转单词）,所以总复杂度也是O(n)，比起上一种方法并没有提高，甚至还多扫描了一次，不过空间上这个不需要额外的存储一份字符串，不过从量级来说也还是O(n)。(用C语言要求实现此方法在O(1)的空间)

我后面用java，测试了一下数组的写法。当练练手，无法通过题目的测试。

3 代码

	/*

	 * Time:O(n) Space:O(n)

	 */

	public String reverseWords(String s) {

		String[] words = s.trim().split("\\s+");

		int size = words.length - 1;

		String res = words[size];

		for (int i = size - 1; i >= 0; i--) {

			res = res + " " + words[i];

		}

		return res;

	}

用数组来体会一下，另外一种思路。

public void reverseWords1(char[] chs) {

		int len = chs.length;

		// 1.过滤掉前后多余的空格

		int left = 0, right = len - 1;

		for (int i = 0; i < len && (chs[i] == ' '); i++) {

			left++;

		}

		for (int i = len - 1; i >= 0 && (chs[i] == ' '); i--) {

			right--;

		}

		// System.out.println("left:"+ left + " right:" + right);

		// 2.过滤掉中间冗余的空格

		int newLen = right - left + 1;

		int index = 0;

		chs[index] = chs[left];

		for (int i = left + 1; i <= right; i++) {

			if (chs[i] == ' ' && chs[i] == chs[index]) {

				continue;

			} else {

				index++;

				chs[index] = chs[i];

				// System.out.println(chs[index]);

			}

		}

		// System.out.println("newString：" + Arrays.toString(chs));

		// 3.反转整个字符串，然后在反转其中的单词。

		reverse(chs, 0, newLen - 1);

		// System.out.println("newString：" + Arrays.toString(chs));

		// System.out.println("newLen:" + newLen);

		for (int i = 0, last = 0; i < newLen; i++) {

			if ( i == newLen || chs[i] == ' ') {

				reverse(chs, last, i - 1);

				last = i + 1;

			}

		}

		System.out.println("res:" + Arrays.toString(chs));

	}

4 总结

考察字符串的操作。

扩展

Reverse Words in a String II：要求用常量空间。

该题在LeetCode中假设开头和结尾没有空格，而且单词之间只有一个空格。但其实不需要这些假设也是可以的，就是代码会比较复杂。

思路就是两步走，第一步就是将整个字符串翻转。然后从头逐步扫描，将每个遇到单词再翻转过来。

注意事项

1）如果是Java，应该跟面试官指出String是immutable，所以需要用char array来做。

2）follow-up问题：k-step reverse。也就是在第二部翻转的时候，把k个单词看作一个长单词，进行翻转。

巴特西

leetcode面试准备:Reverse Words in a String

leetcode面试准备:Reverse Words in a String

1 题目

2 思路

3 代码

4 总结

扩展

最新文章

热门文章