most efficiently reverse the order of words in the sentence


  • 3

    You are given an array of characters arr, which consists of sequences of characters (words) separated by space characters.

    How can you most efficiently reverse the order of words in the sentence?
    For example:
    [ 'p', 'e', 'r', 'f', 'e', 'c', 't', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]

    would turn into:
    [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'e', 'r', 'f', 'e', 'c', 't' ]


  • 5
    S
    void reverse(vector<char>& sentence) {
        reverse(sentence.begin(), sentence.end());
        auto _begin = sentence.begin();
        for(auto itr = sentence.begin(); itr != sentence.end(); itr++)
        {
            if(*itr == ' ')
            {
                reverse(_begin, itr);
                _begin = itr;
                _begin++;
            }    
        }
        reverse(_begin, sentence.end()); 
    }
    

  • 7
    R
    private static char[] reverseOrder(char[] wordsArr){
    		StringBuffer currentString = new StringBuffer();
    		StringBuffer resultString = new StringBuffer();
    		
    		for(int i=wordsArr.length-1;i>=0;i--){
    			if(wordsArr[i]!=' ')
    				currentString.append(wordsArr[i]);
    				
    			if(wordsArr[i]==' ' || i==0)
    			{
    				resultString.append(currentString.reverse());
    				resultString.append(" ");
    				currentString=new StringBuffer();
    			}
    		}
    		return resultString.toString().toCharArray();
    	}
    

  • 0
    public static char[] reverse(char[] input) {
    	int len = input.length;
    	
    	char[] output = new char[len];
    	
    	int previousInputSavepoint = 0;
    	int previousOutputSavepoint = len;
    	boolean continueCopy = false;
    	
    	for (int idx = 0; idx < len; idx ++) {
    		if (Character.isWhitespace(input[idx]) || continueCopy) {
    			int effectiveLength = idx - previousInputSavepoint;
    			System.arraycopy(input, previousInputSavepoint, output, (previousOutputSavepoint - effectiveLength) , effectiveLength);
    			previousInputSavepoint = idx;
    			previousOutputSavepoint -= effectiveLength;
    			continueCopy = true;
    		}
    		
    		if (Character.isLetter(input[idx]) && continueCopy) 
    			continueCopy = false;
    	}
    
    	System.arraycopy(input, previousInputSavepoint, output, 0 , len - previousInputSavepoint);
    	return output;
    }

  • 0
    G

    ...
    public char[] reverseString(char array[]) {
    String input = new String(array);

    	StringTokenizer str = new StringTokenizer(input, " ");
    	StringBuffer lastString = new StringBuffer();
    	StringBuffer curString = new StringBuffer();
    	while(str.hasMoreTokens()) {
    		String temp = str.nextToken();
    		if(lastString.length()==0) {
    			lastString.append(temp);
    		}
    		else {
    			curString.append(temp).append(" ").append(lastString.toString());
    			lastString.delete(0, lastString.length());
    			lastString.append(curString.toString());
    			curString.delete(0,curString.length() );
    		}
    	}
    	return lastString.toString().toCharArray();
    }
    

    ...


  • 0
    N

    JS:

    function reverse(sentence) {
        let cur = [];
        let words = [];
        let output = [];
    
        sentence.forEach(char => {
            if (char === ' ') {
                if (words.length) cur.push(' ');
                words.push(cur);
                cur = [];
            } else {
                cur.push(char);
            }
        });
        cur.push(' ');
        words.push(cur);
        
        while(words.length) {
            output.push(...words.pop());
        }
    
        return output;
    }
    

  • 0

    I am a little confused. is the question to convert the string "perfect makes practice" to "practice makes perfect"? thanks


  • 0
    N

    @qiuping345 Yes, but the input is in the form of a C-string (array of characters)


  • 3
    G

    I think we can reverse each word first, and then reverse the whole char array. Is that correct?

    For example:

    This is a test line ->
    sihT si a tset enil ->
    line test a is This.


  • 0
    N

    @gschengcong Yes, that works too.


  • 3

    3 Line Python, will my code be thought as hacky or concise?

    class Solution(object):
        def reverse_the_order_of_words(self, wordsList):
            words = ''.join(wordsList).split()
            words = words[::-1]
            return list(' '.join(words))
    

  • 0
    B
    public class ReverseWords {
    	public static void main(String[] args) {
    		char a[] = {'p', 'e', 'r', 'f', 'e', 'c', 't', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' };
    		StringBuilder builder = new StringBuilder();
    		int index = 0;
    		for (int i = a.length-1; i >= 0 ; i-- ) {
    			if (a[i] != ' ') {
    				builder.insert(index, a[i]);
    			} else {
    				builder.append(" ");
    				index = builder.length();
    			}
    		}
    		System.out.println(builder.toString());
    	}
    }
    

  • 2
    N

    This way maybe ?

    function reverseWord(arr){
       return arr.join("").split(" ").reverse().join(" ");
    }
    

  • 0
    M

    @nowy Since you need to print back out the array, you can recreate that array using Array.from(). MDN Source

    function reverseWord(arr){
       return Array.from(arr.join("").split(" ").reverse().join(" "));
    }
    

  • 0
    R
    
    def reverseWords(l):
        words = ''.join(l)
        splitwords = words.split(' ')[::-1]
        revised = list(' ' .join(splitwords))
        return revised
        
    print(reverseWords(l))

  • 0

    C#

    public string ReverseWords(char[] c)
    {
        string s = new string(c);
        string result = "";
        string[] split = s.Split(' ');
        for(int i = split.Length - 1; i >= 0; i--)
        {
            result += split[i];
        }
    
    return result;
    }
    
    

  • 0

    Assuming the word input is given as a char list since strings are immutable in python. Reverse whole char array then reverse individual words

    def reverse(s, i, j):
        while i < j:
            s[i], s[j] = s[j], s[i]
            i, j = i + 1, j - 1
    
    def reverse_words(s):
        reverse(s, 0, len(s)-1)
        i = j = 0
        while i < len(s):
            if j == len(s) - 1 or s[j+1] == ' ':
                reverse(s, i, j)
                i = j = j + 2 # j + 1 is either end of string or blank
            else:
                j += 1
        return s
    

  • 0
    F

    @Ipeq1

    Nice! but two line is enough:

        def reverse_the_order_of_words(self, wordsList):
            return ''.join(wordsList).split()[::-1]

  • 0
    S
    This post is deleted!

  • 0
    S

    Reverse the array -

    [ 'p', 'e', 'r', 'f', 'e', 'c', 't', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]
    [ 'e', 'c', 'i', 't', 'c', 'a', 'r', 'p ', ' ', 's', 'e', 'k', 'a', 'm', ' ', 't', 'c', 'e', 'f', 'r', 'e', 'p' ]

    Now break by space, and reverse individual sections
    [ 'e', 'c', 'i', 't', 'c', 'a', 'r', 'p ', ' ', 's', 'e', 'k', 'a', 'm', ' ', 't', 'c', 'e', 'f', 'r', 'e', 'p' ]
    [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e ', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'e', 'r', 'f', 'e', 'c', 't' ]

    Of course not sure if it "efficient", it is 3*O(n), first time reverse whole array, second time, find spaces, third time reverse words

    def reverse(buf, begin, end):
      while begin <= end:
           tmp = buf[begin]
           buf[begin] = buf[end]
           buf[end] = x
    
    def reverse_words(buf):
      n = len(buf)
      reverse(buf,0,n-1) # this could have been done buf = buf[::-1] but wouldn't be O(1) space
    begin = 0 
    index = -1
      while True: # bad practice but still doing it for speed
         index = buf[begin:].index(' ') # get index of space
         if index == -1: # no space left!
             break
         reverse(buf,begin, index-1) # consider if space is at beginning of array?
    

    All of this could be done simply in python if space is no constraint:

    def reverse_words(buf):
       x = ''.join(buf)
       x = x.split()[::-1]
       buf = list(' '.join(x))

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.