翻转字符串中的单词

叁歲伎倆 2022-08-26 04:45 165阅读 0赞

本题目来自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() ;
    		}
    	};
    
    };

[click to show clarification.]: http://oj.leetcode.com/problems/reverse-words-in-a-string/#