首页 > 代码库 > Reverse Words in a String

Reverse Words in a String

2024-07-18 11:01:13   217人阅读

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.

 

 方法一：切割字符串，依次将word放入数组中，然后在逆序输出，时间复杂度为O(n)，空间复杂度为O(n)，代码如下：

 1 class Solution { 2 public: 3     void reverseWords(string &s) { 4         int start = s.find_first_not_of(‘ ‘);   //找到第一个非空格字母 5         vector<string> vstr; 6         while( start != string::npos ) {    //若不是字符串结尾处 7             int pos = s.find_first_of(‘ ‘, start);  //从start开始找，找到第一个空格 8             vstr.push_back( s.substr(start, pos-start) );   //切割字符串，放入向量中 9             start = s.find_first_not_of(‘ ‘, pos);  //pos出开始找第一个非空格10         }11         s.clear();12         if( vstr.empty() ) return ;13         s.append(vstr[vstr.size()-1]);14         for(int i=vstr.size()-2; i>=0; --i) {   //从后往前依次将字母放入string中15             s.push_back(‘ ‘);16             s.append(vstr[i]);17         }18     }19 };

 

方法二：原地反转字母，首先去除首部和尾部空格，去除单词与单词之间多余的空格，然后反转整个字符串，在接着依次反转每个单词，时间复杂度为O(n)，空间复杂度为O(1)，代码如下：

 

 1 class Solution { 2 public: 3     void reverseWords(string &s) { 4         char* buf = new char[s.length()+1]; 5         strcpy(buf, s.c_str()); 6         reverseCWords(buf); 7         s = buf; 8         delete[] buf; 9     }10 11     void reverseCWords(char* s) {12         int k=0;13         int i=0;14         while( s[i] && s[i] == ‘ ‘ ) ++i;   //寻找第一个非空格字符15         for(; s[i]; ++i) {16             if( s[i] != ‘ ‘ )       //若s[i]为非空格17                 s[k++] = s[i];18             else if( s[k-1] != ‘ ‘ )    //若前一个字符是非空格19                     s[k++] = ‘ ‘;20         }21         if( s[k-1] == ‘ ‘ ) --k;    //若最后一个字符是空格，则去掉22         s[k] = 0;23         reverse(s, s+k);    //反转整个字符串24         char* start = s;25         char* end = s+k;26         while( start < end ) {27             char* pos = find(start, end, ‘ ‘); 28             reverse(start, pos);    //依次反转每个单词29             start = pos+1;30         }31     }32 };

 

 


联系
我们