首页 > 试题广场 >

翻转单词序列

[编程题]翻转单词序列

热度指数：687898 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

数据范围： $1 \leq n \leq 100 \$
进阶：空间复杂度 $O(n) \$ ，时间复杂度 $O(n) \$ ，保证没有只包含空格的字符串

示例1

输入

"nowcoder. a am I"

输出

"I am a nowcoder."

示例2

输入

""

输出

""

算法知识视频讲解

推荐

嗷嗷兽

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();
    }
}

编辑于 2015-06-19 17:23:02 回复(45)

牛客000001号

//翻转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;
    }

发表于 2015-07-23 22:45:50 回复(15)

魅影骑士

/*
	算法思想：先翻转整个句子，然后，依次翻转每个单词。
    依据空格来确定单词的起始和终止位置
*/
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--;
        }
    }
}

发表于 2017-03-06 11:38:00 回复(13)

彭延

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

编辑于 2015-09-25 00:53:32 回复(8)

offer收割机`

看哥简洁的代码，反转两次：
#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;
    }
};

发表于 2016-12-03 22:09:02 回复(8)

InnerPeace1203

/*
 * 剑指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--;
	}
    }
}

发表于 2017-09-07 10:45:10 回复(1)

Python

华科平凡

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])

发表于 2017-10-07 17:28:20 回复(6)

drdr

//时间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;
    }
};

编辑于 2017-06-08 14:19:34 回复(2)

nailperry

   解题思路：先翻转每个单词，再翻转整个句子
   细节很重要，要特别考虑到“   ”等输入中包含多余空格的情形 
   方法一：使用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);       
    }

编辑于 2015-08-13 10:18:58 回复(4)

老石基

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();
    }
}

发表于 2016-04-17 13:24:59 回复(1)

搬一块叫CV的砖

//不知不觉刷到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;
}

};

发表于 2016-03-24 23:10:45 回复(3)

C/C++

却顾所来径

虽然蒙对了，有谁能解释一下只有空格的情况。
思路：先反转整个句子，再依次反转每个单词
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]);
    }
};

编辑于 2018-07-06 19:32:47 回复(4)

C/C++

kakaan

原创方法，使用栈实现

很显然，翻转顺序，很显然需要用栈，

    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;
    }

发表于 2016-06-28 18:04:39 回复(6)

Ron

    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();
    }

编辑于 2015-07-09 09:22:57 回复(6)

打工不可能打工的

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;
    }
}

发表于 2018-08-11 13:21:55 回复(0)

~一念执着~

//有两种方法，第一种不改变原来的字符串，新建一个新的串，通过检验空格获取每个单词，然后放//到结果串中去；第二种两次翻转，先整体翻转，然后检测空格，将每个单词翻转
//方法一：
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;      
    }
};

发表于 2017-06-08 14:56:07 回复(0)

小熊与你同行

# -*- 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])

发表于 2018-06-13 11:49:52 回复(2)

C++

柯基肥

class Solution {
public:
string ReverseSentence(string str) {
vector<char> v;
stack<char> s1;
string s;
for(int i=str.size()-1;i>-1;i--){
s1.push(str[i]);
if(str[i-1] == ' '){
while(!s1.empty()){
v.push_back(s1.top());
s1.pop();
}
v.push_back(' ');
i--;
}
if(i == 0){
while(!s1.empty()){
v.push_back(s1.top());
s1.pop();
}
}
}
s.assign(v.begin(),v.end());
return s;
}
};

发表于 2021-07-19 12:17:33 回复(0)

灵正韵则

    public String ReverseSentence(String str) {
        if (str == null || str.length() == 0) {
            return str;
        }
        char[] chars = str.toCharArray();
        //整个句子反转
        reverse(chars, 0, chars.length-1);
        int start = 0, end = 0;
        //分别反转里面的单词
        while (end < chars.length){
            //碰到空格了，将里面的单次反转
            if (chars[end] == ' '){
                reverse(chars, start, end-1);
                start = end+1;
                end++;
            }
            //到最后一个，反转前面的单次
            else if (end == chars.length-1){
                reverse(chars, start, end);
                end++;
            }else {
                end++;
            }
        }

        return String.valueOf(chars);
    }

    /**
     * 反转方法
     * @param target
     * @param start
     * @param end
     */
    private void reverse(char[] target, int start, int end){
        while (start < end){
            char tmp = target[start];
            target[start] = target[end];
            target[end] = tmp;
            start++;
            end--;
        }
    }

发表于 2020-02-06 19:41:03 回复(0)

墩儿

python的两次翻转解法

class Solution:
    def ReverseSentence(self, s):
        # write code here
        low, high, tmp = 0, 0, 1
        s += ' '
        s = list(s)
        for i in s:
            if i != ' ':
                high += 1
                tmp = high + 1
            else:
                high -= 1
                while low <= high:
                    s[low], s[high] = s[high], s[low]
                    low += 1
                    high -= 1
                low = tmp
                high = tmp
        s.pop()
        return ''.join(s[::-1])

发表于 2019-04-29 20:14:21 回复(1)

Java

Mr.『黑』℡

/*
  算法思想：先翻转整个句子，然后，依次翻转每个单词。
    依据空格来确定单词的起始和终止位置
*/
public class Solution {
    public String ReverseSentence(String str) {
        char [] chars = str.toCharArray ();
        int start = 0 ;
        int end = 0 ;
        //整体反转
        process ( chars , 0 , chars.length - 1 );
        
        //遇到空格，即认定为一个单词，然后对单词进行反转
        for ( int i = 0 ; i < chars.length ; ++ i ){
            if ( chars [i] == ' ' ){
                end = i ;//i是空格的位置
                process ( chars , start , end - 1 );
                start = i + 1 ;
            }
        }
        //单独对最后一个单词进行反转
        process ( chars , start , chars.length - 1 );
        
        return new String ( chars );
    }
    
     public void process ( char [] chars , int start , int end ){
        while ( start < end ){
            swap ( chars , start , end );
            start++;
            end--;
        }
    }
    
    public void swap ( char [] chars , int start , int end ){
        char temp = chars [start];
        chars [start] = chars [end];
        chars [end] = temp ;
    }
}

发表于 2018-05-29 17:48:22 回复(1)