LeetCode: Reverse Words in a String

题目:

https://oj.leetcode.com/problems/reverse-words-in-a-string/

分析:

解法一:(相比较更麻烦点)

  1. 运用栈来解题, 先把s中的一个个单词解析出来压到栈里, 然后再出栈重组成s

  2. 有一些特殊的边界需要考虑, 比如连续出现两个空格, 单词的头尾部出现空格等等, 这些情况需要特殊处理一下。

解法二:(更巧妙, 推荐)

从后向前进行循环

    处理空格部分

    如果结果res非空, 插入一个空格

    处理非空格部分

代码:

解法一:

class Solution
{
public:
	void reverseWords(string &s)
	{
		if (s.empty())
			return;

		string word;
		stack<string> stk;
		s.push_back(' ');
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] != ' ')
				word.push_back(s[i]);
			else if (i > 0 && s[i] == ' ' && s[i-1] != ' ')
			{
				stk.push(word);
				word.clear();
			}
		}

		s.clear();
		if (stk.empty())
			return;
		while (true)
		{
			s += stk.top();
			stk.pop();
			if (stk.empty())
				break;
			else
				s.push_back(' ');
		}
		return;
	}
};

解法二:

class Solution
{
public:
	void reverseWords(string &s)
	{
		string res;

		int i = s.size() - 1;
		while (true)
		{
			while (s[i] == ' ' && i >= 0) 
				i--;
			if (i < 0) break;

			if (!res.empty())
				res.push_back(' ');

			string temp;
			while (s[i] != ' ' && i >= 0) 
			{
				temp.push_back(s[i]);
				i--;
			}
			reverse(temp.begin(), temp.end());
			res += temp;
			if (i < 0) break;
		}
		s = res;
	}
};

参考:

http://blog.csdn.net/kenden23/article/details/20701069

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39138373

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();