LeetCode Reverse Words in a String

LeetCode 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".

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

click to show clarification.

Clarification:

  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.

对一个字符串,以单词为单位进行逆序。注意字符串中可能会有多个连续的空格,还可能在首尾有空格。

如果允许使用额外的空间,那就好办,先把字符串分词,然后逆序拼接。代码如下:

class Solution {
public:
	void reverseWords(string &s) {
		string ans = "";
		int start = 0, end = 0, n = s.size();
		while (true) {
			while (start < n&&s[start] == ' ')++start;
			if (start >= n)break;
			end = start + 1;
			while (end < n&&s[end] != ' ')++end;
			if (end >= n)break;
			ans = s.substr(start, end - start) + " " + ans;
			start = end + 1;
		}
		if (end > start)ans = s.substr(start, end - start) + " " + ans;
		s = ans.substr(0, ans.size() - 1);
	}
};

本代码提交AC,用时9MS。

如果不借助额外空间,则只能在原字符串上进行逆序了,有意思。我们可以进行两次翻转,第一次对整个字符串翻转,然后遍历新字符串,对每个单词进行翻转。比如原字符串是"the sky is blue",第一次翻转之后就是"eulb si yks eht",再依次对每个单词翻转,就变成了"blue is sky the"。

我们知道对一个字符串进行翻转可以使用首尾指针的方法in-place实现,代码中为了可读性,直接调用了STL的reverse函数。

class Solution {
public:
	void reverseWords(string &s) {
		reverse(s.begin(), s.end());
		//i,j为新字符串每个单词的首尾位置,u,v为旧字符串每个单词的首尾位置
		int i = 0, j = 0, u = 0, v = 0, n = s.size();
		while (true) {
			while (u < n&&s[u] == ' ')++u;
			if (u >= n)break;
			v = u;
			while (v < n&&s[v] != ' ')s[j++] = s[v++];
			reverse(s.begin() + i, s.begin() + j);
			if (v >= n)break;
			s[j++] = ' ';
			i = j;
			u = v;
		}
		if (j == 0)s = "";
		else if (s[j - 1] == ' ')s.resize(j - 1);
		else s.resize(j);
	}
};

本代码提交AC,用时6MS。虽然第二种方法更快,也更省空间,但是有很多边界条件很容易出错,我还是觉得第一种方法安全。

参考:http://www.cnblogs.com/grandyang/p/4606676.html

Leave a Reply

Your email address will not be published. Required fields are marked *