现在的位置: 首页 > 综合 > 正文

翻转字符串中的单词

2018年02月01日 ⁄ 综合 ⁄ 共 1360字 ⁄ 字号 评论关闭

本题目来自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.
我的思路:
1.可以使用先翻转每一个单词,然后再对整个字符串进行整体翻转。
          这种方法针对本题目有个缺点,由于要求“your reversed string should not contain leading or trailing spaces.”并且
Reduce them to a single space in the reversed string.”, 因此在对字符串完成整体翻转之后还需要额外的处理,去掉前后的空格,将单词间多个空格换成一个。
2.借住辅助栈,从前向后将单词逐个入栈,然后再逐个出栈,放入结果字符串中,同时两个字符串之间用空格隔开。
这两种算法的时间复杂度都是O(n),是第二种方法的空间复杂度较高,但是从时间复杂度上来说,第二种方法的常数项要小,因此第二种方法的时间复杂度更好些。同时第二种方法处理简单,不需要对字符串中的空格进行繁琐的处理。
下面贴出AC过的代码,如有问题,欢迎大家批评指正:
class Solution {
public:
	void reverse(string&s, int start, int end) 
	{
		if (start >= end - 1) return ;
		std :: reverse(s.begin() + start, s.begin() + end ) ;
	} ;
	void reverseWords(string &s) {
		stack<string> words ;
		int start = 0 ;
		int end = 0 ;
		while (true)
		{
			start = s.find_first_not_of(' ', end) ;
			if (start == string :: npos) break ;
			end = s.find_first_of(' ', start) ;
			if (end == string :: npos)
				end = s.length() ;
			words.push(s.substr(start, end - start)) ;
			if (end == s.length())
				break ;
		}
		s.clear() ;
		if (!words.empty())
		{
			while (words.size() > 1)
			{
				s.append(words.top()) ;
				words.pop() ;
				s.append(" ") ;
			}
			s.append(words.top()) ;
			words.pop() ;
		}
	};

};

抱歉!评论已关闭.