[编程题]翻转单词顺序列
• 热度指数：429883 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

```public class Solution {
public String ReverseSentence(String str) {
if(str.trim().equals("")){
return str;
}
String[] a = str.split(" ");
StringBuffer o = new StringBuffer();
int i;
for (i = a.length; i >0;i--){
o.append(a[i-1]);
if(i > 1){
o.append(" ");
}
}
return o.toString();
}
}
```

```//翻转str从s到e的部分
void ReverseWord(string &str, int s, int e)
{
while(s < e)
swap(str[s++], str[e--]);
}

string ReverseSentence(string str) {
ReverseWord(str, 0, str.size() - 1); //先整体翻转
int s = 0, e = 0;
int i = 0;
while(i < str.size())
{
while(i < str.size() && str[i] == ' ') //空格跳过
i++;
e = s = i; //记录单词的第一个字符的位置
while(i < str.size() && str[i] != ' ') //不是空格 找单词最后一个字符的位置
{
i++;
e++;
}
ReverseWord(str, s, e - 1); //局部翻转
}
return str;
}```

```class Solution {
public:
string ReverseSentence(string str) {
string res = "", tmp = "";
for(unsigned int i = 0; i < str.size(); ++i){
if(str[i] == ' ') res = " " + tmp + res, tmp = "";
else tmp += str[i];
}
if(tmp.size()) res = tmp + res;
return res;
}
}; ```

python版本
```class Solution:
def ReverseSentence(self, s):
return " ".join(s.split()[::-1]) if s.strip() != "" else s```

```/*
算法思想：先翻转整个句子，然后，依次翻转每个单词。
依据空格来确定单词的起始和终止位置
*/
public class Solution {
public String ReverseSentence(String str) {
char[] chars = str.toCharArray();
reverse(chars,0,chars.length - 1);
int blank = -1;
for(int i = 0;i < chars.length;i++){
if(chars[i] == ' '){
int nextBlank = i;
reverse(chars,blank + 1,nextBlank - 1);
blank = nextBlank;
}
}
reverse(chars,blank + 1,chars.length - 1);//最后一个单词单独进行反转
return new String(chars);

}
public void reverse(char[] chars,int low,int high){
while(low < high){
char temp = chars[low];
chars[low] = chars[high];
chars[high] = temp;
low++;
high--;
}
}
}```

 栈顶 hello 栈底 world！

```public String ReverseSentence(String str) {
if (str.trim().equals("") && str.length() > 0) {
return str;
}
Stack reverse = new Stack();
String string = str.trim();
String[] strings = string.split(" ");
for (int i = 0; i length; i++) {
reverse.push(strings[i]);
}
string = reverse.pop();
while (!reverse.isEmpty()) {
string = string + " " + reverse.pop();
}
return string;
}```

```使用递归 一行代码；
public class Solution {
public String ReverseSentence(String str) {
return (str.lastIndexOf(" ")==-1)?str:str.substring(str.lastIndexOf(" ")+1) +" "+ReverseSentence(str.substring(0,str.lastIndexOf(" ")));
}
}```

```class Solution {
public:
string ReverseSentence(string str) {
if (str.empty()) return str;
reverse(str.begin(), str.end());

size_t beg = 0;
size_t end = 0;
while (end != string::npos){
beg = str.find_first_not_of(' ', beg);
end = str.find_first_of(' ', beg);

if (beg == string::npos) return str;
if (end == string::npos)
reverse(str.begin()+beg, str.end());
else
{
reverse(str.begin()+beg, str.begin()+end);
beg = end+1;
}
}

return str;
}
};```

```   解题思路：先翻转每个单词，再翻转整个句子
细节很重要，要特别考虑到“   ”等输入中包含多余空格的情形
方法一：使用split
public String ReverseSentence(String str) {
if(str==null||str.trim().equals(""))// trim掉多余空格
return str;
String[] words = str.split(" ");// 以空格切分出各个单词
StringBuffer buffer = new StringBuffer();
for(int i=0;i<words.length;i++){

buffer.append(reverse1(words[i].toCharArray(), 0, words[i].length()-1)).append(" ");
}
if(buffer.length()>0)
buffer.deleteCharAt(buffer.length()-1);// 删除最后一个空格
return reverse1(buffer.toString().toCharArray(), 0, buffer.length()-1);

}
private String reverse1(char[] str, int l, int r) {
// TODO Auto-generated method stub
if(l>r)
return "";
char tmp;
while(l<r){
tmp = str[l];
str[l] = str[r];
str[r] = tmp;
l++;
r--;
}
return String.valueOf(str);
}
方法二：不使用split
private void reverse(char[] str, int l, int r) {
// TODO Auto-generated method stub
if(l>r)
return;
char tmp;
while(l<r){
tmp = str[l];
str[l] = str[r];
str[r] = tmp;
l++;
r--;
}
}
public String ReverseSentence(String str) {
if(str==null||str.equals(""))
return str;
char[] words = str.toCharArray();
int l=0,r,i=0;
boolean isFirst1 = true;
boolean isFirst2 = true;
while(i<words.length){
if(words[i]!=' '&&isFirst1){
// 定位到第一个不为空的字符
l = i;
isFirst1 = false;
i++;
}else if(words[i]==' '&&isFirst2){
r = i-1;// 定位到单词后的第一个空格
isFirst2 = false;
// 翻转已经截取的单词
reverse(words, l, r);
// 修改标志,定位下一个单词
isFirst1 = true;
isFirst2 = true;
i++;
}else{
i++;
}
}
if(words[words.length-1]!=' '){
reverse(words, l, words.length-1);// 翻转最后一个单词
}
reverse(words, 0, words.length-1);
return String.valueOf(words);
}```

```/*
* 剑指offer的思想：两次翻转
*/
public class Solution {
public String ReverseSentence(String str) {
if(str==null||str.trim().getClass().equals(""))
return str;
char[] c=str.toCharArray();

reverse(c, 0, str.length()-1);//翻转整个句子

//翻转句子中的每个单词
int begin=0;
int end=0;
while(begin!=c.length){//若起始字符为空格，则begin和end都自加
if(c[begin]==' '){
begin++;
end++;
}
else if(c[end]==' '){//遍历到终止字符为空格，就进行翻转
reverse(c, begin, --end);
begin=++end;
}
else if(end==c.length-1){//若遍历结束，就进行翻转
reverse(c, begin,end);
begin=++end;
}
else{//没有遍历到空格或者遍历结束，则单独对end自减
end++;
}
}

return String.valueOf(c);
}

//完成翻转功能
private void reverse(char[] c,int begin,int end){
while(begin<end){
char temp=c[begin];
c[begin]=c[end];
c[end]=temp;

begin++;
end--;
}
}
}```

```看哥简洁的代码，反转两次：
#include<algorithm>
class Solution {
public:
string ReverseSentence(string str) {
std::reverse(str.begin(),str.end());
int front=0;
int back=0;
int size = str.size();
while(front<size){
while(front<size&&str[front]==' ')++front;
back=front;
while(back<size&&str[back]!=' ')++back;
std::reverse(str.begin()+front, str.begin()+back);
front=back;
}
return str;
}
};```

# python solution.

split funciton should have a para. If not, there will be an error.

``````# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):

return " ".join(s.split(" ")[::-1])
``````

```//时间O(n),空间O(1)。
//两次翻转，第一次整体翻转，第二次每个单词再翻转。
class Solution {
public:
string ReverseSentence(string str) {
reverse(str.begin(), str.end());
string::size_type s = 0, e;
while((e=str.find(' ', s)) != string::npos){
reverse(str.begin()+s, str.begin()+e);
s = e + 1;
}
reverse(str.begin()+s, str.end());
return str;
}
};```

```# -*- coding:utf-8 -*-

class Solution:
"""
Problem:
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。
同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。
例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，
正确的句子应该是“I am a student.”。
Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
-----------------------------------------
Think:
1、直接法，直接分割字符串，然后反序拼接
2、对所有的字符进行翻转，然后对整个字符串进行翻转。python不好实现。
3、堆栈思想，反转字符串，先进后出，就是反转了

-----------------------------------------
Idea:
1、直接分割字符串，然后反序拼接
2、使用堆栈先进后出的规则，反转字符串

-----------------------------------------
Code[1]:
def ReverseSentence(self, s):
alist = s.split(" ")
alist.reverse()
return " ".join([x for x in alist])

-----------------------
运行时间：37ms
占用内存：5752k
量级:O（n）
空间：n
优点：很容易想到并实现
缺点：需要多余的额外空间

-----------------------------------------
Code[2]:
def ReverseSentence(self, s):
alist = s.split(" ")
stacklist = []
for i in alist:
stacklist.append(i)
result = []
while len(stacklist) > 0:
result.append(stacklist.pop())
return " ".join([x for x in result])

-----------------------
运行时间：29ms
占用内存：5612k
量级:O（n）
空间：2n
优点：容易理解，而且比较巧妙
缺点：需要多余的额外空间

"""
def ReverseSentence(self, s):
alist = s.split(" ")
stacklist = []
for i in alist:
stacklist.append(i)
result = []
while len(stacklist) > 0:
result.append(stacklist.pop())
return " ".join([x for x in result])
```

```class Solution {
public:
string ReverseSentence(string str) {
int len = str.size(), i = str.size() - 1;
while(i >= 0){
stack<char> tmp;
while(i >= 0 && str[i] != ' '){
tmp.push(str[i]); --i;

}
while(!tmp.empty()){
str += tmp.top(); tmp.pop();
}
str += str[i];
--i;
}
return str.substr(len, len);
}
};
```

```public class Solution {
public String ReverseSentence(String str) {
if(str==null||str.length()==0||str.trim().length()==0)
return str;
StringBuffer sb = new StringBuffer();
String[] s = str.trim().split(" ");
for(int i = s.length-1;i>=0;i--){
if(s[i]!="")
sb.append(s[i]);
if(i-1>=0)
sb.append(" ");
}
return sb.toString();
}
}```

```//不知不觉刷到42题了，这道题主要思想就是先翻转所有字符，再逐个单词翻转，逐个单词翻转的时候考虑三种不同情况即可。
class Solution {
public:
void Reverse(string& sent, int begin, int end)
{
if (begin<0 || end<0)
return;
while (begin<end)
{
char c;
c = sent[begin];
sent[begin] = sent[end];
sent[end] = c;
begin++;
end--;

}
}
string ReverseSentence( string &str) {
int length = str.size();

if (length <= 1)
return str;
int pBegin = 0;
int pEnd = 0;
while (str[pEnd] != '\0')
{
pEnd++;
}
pEnd--;
Reverse(str, pBegin, pEnd);

pBegin = pEnd = 0;
while (str[pBegin] != '\0')
{
if (str[pBegin] == ' ')
{
pBegin++;
pEnd++;
}
else if (str[pEnd] == ' ' || str[pEnd] == '\0')
{
Reverse(str, pBegin, --pEnd);
pBegin = ++pEnd;
}
else
{
pEnd++;
}
}
return str;
}

};```

```    string ReverseSentence(string str) {
stack<string> Words;
int currBlankPos = 0;
int perBlankPos = 0;
string subString;
while (currBlankPos>=0)
{
currBlankPos = str.find_first_of(' ', perBlankPos); // 找到空格分隔字符串（找到word压如栈里头）
subString = str.substr(perBlankPos, currBlankPos < 0 ? (str.length() - perBlankPos) : currBlankPos - perBlankPos); // 按长度截取单词
perBlankPos = currBlankPos + 1;
Words.push(subString); //把单词压如栈
}
subString.clear();
while (!Words.empty())
{
subString += Words.top(); Words.pop();
if(!Words.empty()) subString += " "; // 需不需要加空格
}
return subString;
}```

```    public static String ReverseSentence(String str) {
StringBuffer sb = new StringBuffer("");
if(str.length() <= 0 || str.trim().equals("")){
//要trim()，可能输入多个空格组成的字符串
return str;
}
String[] strSet = str.split(" ");
int length = strSet.length;
for(int i = length-1; i > 0 ;i--){
sb.append(strSet[i]+" ");
}
sb.append(strSet[0]);
return sb.toString();
}```

```public class Solution {
public String ReverseSentence(String str) {
if (str.split(" ").length < 1 || str == null || str == "") {
return str;
}
String resString = "";
String[] arr = str.split(" ");
int left = 0;
int right = arr.length - 1;
while (left < right) {
String tmp = arr[left];
arr[left++] = arr[right];
arr[right--] = tmp;
}
for (int i = 0; i < arr.length; i++) {
resString += arr[i];
if (i <= arr.length - 2) {
resString += " ";
}
}
return resString;
}
}
```

```虽然蒙对了，有谁能解释一下只有空格的情况。

class Solution {
public:
string ReverseSentence(string str) {
int len=str.size();
if(str[0]==' ')return str;//我改成str==" "为啥不行？
fun(str,0,len-1);//整体反转一次
for(int l=0,r=0;r<=len;){//l设为每个单词开头，r设为每个单词后的空格位置
if(r<len&&str[r]!=' ')r++;//没有到达末尾或者遇到空格
else{//遇到空格或者到末尾
fun(str,l,r-1);
l=++r;
}
}
return str;
}
void fun(string &str,int l,int r){//反转一个字符串
for(int i=l;i<=(l+r)/2;i++)
swap(str[i],str[l+r-i]);
}
};
```

```//有两种方法，第一种不改变原来的字符串，新建一个新的串，通过检验空格获取每个单词，然后放//到结果串中去；第二种两次翻转，先整体翻转，然后检测空格，将每个单词翻转
//方法一：
class Solution {
public:
string ReverseSentence(string str) {
reverse(str.begin(),str.end());
string:: iterator left=str.begin(),right=left;
while(*right!='\0'){
while(*right!='\0'&&*right!=' ')
++right;
reverse(left,right);
if(*right!='\0'){
left=right+1;
right=left;
}
}
return str;
}
};
//方法二：
class Solution {
public:
string ReverseSentence(string str) {
reverse(str.begin(),str.end());
string::size_type left=0,right=0;
while((right=str.find(' ',left))!=str.npos){
reverse(str.begin()+left,str.begin()+right);
left=right+1;
}
reverse(str.begin()+left,str.end());
return str;
}
};
```

952条回答 84182浏览

# 通过挑战的用户

• 2019-12-07 00:47:28
• 2019-12-06 22:49:58
• 2019-12-06 22:23:23
• 2019-12-06 21:11:56
• 2019-12-06 20:59:20

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题