首页 > 代码库 > leetcode之倒转一句话单词

leetcode之倒转一句话单词

题目:

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

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

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.

思路:

这题的思路不用多说,完全是烂大街的题,不就是先以每个单词为单位,进行翻转,再以整句话为单位进行翻转吗?呵呵,太简单了,以为简单你就能做对那可就大错特错了,题干里的的说明还要求去除首尾空格,并压缩多个空格为一个空格,所以会有N多边界条件要考虑,我竟然编译了N次才通过leetcode OJ,作为一个正式工作一年多的程序员,实在是对不起国家,边界条件的确是考察一个人思维严谨性甚至记忆力的试金石!

代码:

class Solution {
public:
	Solution(){}
	void reverse(std::string &s, int f, int e)
	{
		while (e>f)
		{
			char tmp = s.at(f);
			s.at(f) = s.at(e);
			s.at(e) = tmp;
			f++;
			e--;
		}
	}
	void squeeze(std::string &s)
	{
		int i = 0;
		std::string re = "";
		char prev = NULL;
		bool flag = false;
		while (i < s.size())
		{
			if (s.at(i)!=' ')
			{
				if (flag&&prev == ' ')
				{
					re.push_back(' ');
				}
				re.push_back(s.at(i));
			}
			if (s.at(i) == ' '&&prev !=NULL &&prev!= ' ')
			{
				flag = true;
			}
			prev = s.at(i);
			i++;
		}
		s = re;
	}
	void reverseWords(std::string &s) {
		int i = 0;
		int f=0, e=0;
		char prev = ' ';
		while (i<s.size())
		{
			if (prev == ' '&&s.at(i) != ' ')
			{
				f = i;
			}
			if ((s.at(i) == ' '&&prev != ' ') || (i == s.size() - 1 && s.at(i) != ' '))
			{
				if (i == s.size() - 1 && s.at(i) != ' ')
				{
					e = i;
				}
				else
				{
					e = i - 1;
				}
				if (f<e)
				{
					reverse(s, f, e);
				}
			}
			prev = s.at(i);
			i++;
		}
		reverse(s, 0, s.size() - 1);
		squeeze(s);
	}
};


leetcode之倒转一句话单词