<p>Given an array of characters which forms a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.</p>

<p>Example input and output:</p>

<pre><code>&gt;&gt;&gt; reverse_words("this is a string")
'string a is this'
</code></pre>

<p>It should be O(N) time and O(1) space (<code>split()</code> and pushing on / popping off the stack are not allowed).</p>

<p>The puzzle is taken from <a href="http://halcyon.usc.edu/~kiran/msqs.html#programming" rel="noreferrer" title="Microsoft Interview Questions">here</a>.</p>

[{'answer_id': 47416, 'author': 'aku', 'author_id': 1196, 'author_profile': 'https://Stackoverflow.com/users/1196', 'pm_score': 1, 'selected': False, 'text': '<p>In pseudo code:</p>\n\n<pre><code>reverse input string\nreverse each word (you will need to find word boundaries)\n</code></pre>\n'}, {'answer_id': 47419, 'author': 'Joel Coehoorn', 'author_id': 3043, 'author_profile': 'https://Stackoverflow.com/users/3043', 'pm_score': 0, 'selected': False, 'text': '<p>Push each word onto a stack.  Pop all the words off the stack.</p>\n'}, {'answer_id': 47423, 'author': 'smh', 'author_id': 1077, 'author_profile': 'https://Stackoverflow.com/users/1077', 'pm_score': 1, 'selected': False, 'text': '<p>In C: (C99)</p>\n<pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt;\n#include &lt;string.h&gt;\n\nvoid reverseString(char* string, int length)\n{\n    char swap;\n    for (int i = 0; i &lt; length/2; i++)\n    {\n        swap = string[length - 1 - i];\n        string[length - 1 - i] = string[i];\n        string[i] = swap;\n    }   \n}\n\nint main (int argc, const char * argv[]) {\n    char teststring[] = &quot;Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.&quot;;\n    printf(&quot;%s\\n&quot;, teststring);\n    int length = strlen(teststring);\n    reverseString(teststring, length);\n    int i = 0;\n    while (i &lt; length)\n    {\n        int wordlength = strspn(teststring + i, &quot;ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz&quot;);\n        reverseString(teststring + i, wordlength);\n        i += wordlength + 1;\n    }\n    printf(&quot;%s\\n&quot;, teststring);\n    return 0;\n}\n</code></pre>\n<p>This gives output:</p>\n<blockquote>\n<p>Given an array of characters which\nform a sentence of words, give an\nefficient algorithm to reverse the\norder of the words (not characters) in\nit.</p>\n<p>.it in )characters not( words the\nof order the reverse to algorithm\nefficient an give ,words of sentence a\nform which characters of array an\nGiven</p>\n</blockquote>\n<p>This takes at most 4N time, with small constant space.\nUnfortunately, It doesn\'t handle punctuation or case gracefully.</p>\n'}, {'answer_id': 47424, 'author': 'jfs', 'author_id': 4279, 'author_profile': 'https://Stackoverflow.com/users/4279', 'pm_score': 1, 'selected': False, 'text': '<p>O(N) in space and O(N) in time solution in Python:</p>\n\n<pre class="lang-py prettyprint-override"><code>def reverse_words_nosplit(str_):\n  """\n  &gt;&gt;&gt; f = reverse_words_nosplit\n  &gt;&gt;&gt; f("this is a string")\n  \'string a is this\'\n  """\n  iend = len(str_)\n  s = ""\n  while True:\n    ispace = str_.rfind(" ", 0, iend)\n    if ispace == -1:\n      s += str_[:iend]\n      break\n    s += str_[ispace+1:iend]\n    s += " "\n    iend = ispace\n  return s\n</code></pre>\n'}, {'answer_id': 47426, 'author': 'Thomas Watnedal', 'author_id': 4059, 'author_profile': 'https://Stackoverflow.com/users/4059', 'pm_score': 6, 'selected': True, 'text': '<p>A solution in C/C++:</p>\n\n<pre class="lang-cpp prettyprint-override"><code>void swap(char* str, int i, int j){\n    char t = str[i];\n    str[i] = str[j];\n    str[j] = t;\n}\n\nvoid reverse_string(char* str, int length){\n    for(int i=0; i&lt;length/2; i++){\n        swap(str, i, length-i-1);\n    }\n}\nvoid reverse_words(char* str){\n    int l = strlen(str);\n    //Reverse string\n    reverse_string(str,strlen(str));\n    int p=0;\n    //Find word boundaries and reverse word by word\n    for(int i=0; i&lt;l; i++){\n        if(str[i] == \' \'){\n            reverse_string(&amp;str[p], i-p);\n            p=i+1;\n        }\n    }\n    //Finally reverse the last word.\n    reverse_string(&amp;str[p], l-p);\n}\n</code></pre>\n\n<p>This should be O(n) in time and O(1) in space.</p>\n\n<p>Edit: Cleaned it up a bit.</p>\n\n<p>The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.</p>\n'}, {'answer_id': 47434, 'author': 'Xian', 'author_id': 4642, 'author_profile': 'https://Stackoverflow.com/users/4642', 'pm_score': 1, 'selected': False, 'text': '<p>You would use what is known as an iterative recursive function, which is O(N) in time as it takes N (N being the number of words) iterations to complete and O(1) in space as each iteration holds its own state within the function arguments.  </p>\n\n<pre class="lang-scm prettyprint-override"><code>(define (reverse sentence-to-reverse)\n  (reverse-iter (sentence-to-reverse ""))\n\n(define (reverse-iter(sentence, reverse-sentence)\n  (if (= 0 string-length sentence)\n    reverse-sentence\n    ( reverse-iter( remove-first-word(sentence), add-first-word(sentence, reverse-sentence)))\n</code></pre>\n\n<p><em>Note: I have written this in scheme which I am a complete novice, so apologies for lack of correct string manipulation.</em></p>\n\n<p>remove-first-word finds the first word boundary of sentence, then takes that section of characters (including space and punctuation) and removes it and returns new sentence</p>\n\n<p>add-first-word finds the first word boundary of sentence, then takes that section of characters (including space and punctuation) and adds it to reverse-sentence and returns new reverse-sentence contents.</p>\n'}, {'answer_id': 47435, 'author': 'Ferruccio', 'author_id': 4086, 'author_profile': 'https://Stackoverflow.com/users/4086', 'pm_score': 0, 'selected': False, 'text': '<p>A C++ solution:</p>\n\n<pre class="lang-cpp prettyprint-override"><code>#include &lt;string&gt;\n#include &lt;iostream&gt;\nusing namespace std;\n\nstring revwords(string in) {\n    string rev;\n    int wordlen = 0;\n    for (int i = in.length(); i &gt;= 0; --i) {\n        if (i == 0 || iswspace(in[i-1])) {\n            if (wordlen) {\n                for (int j = i; wordlen--; )\n                    rev.push_back(in[j++]);\n                wordlen = 0;\n            }\n            if (i &gt; 0)\n                rev.push_back(in[i-1]);\n        }\n        else\n            ++wordlen;\n    }\n    return rev;\n}\n\nint main() {\n    cout &lt;&lt; revwords("this is a sentence") &lt;&lt; "." &lt;&lt; endl;\n    cout &lt;&lt; revwords("  a sentence   with extra    spaces   ") &lt;&lt; "." &lt;&lt; endl;\n    return 0;\n}\n</code></pre>\n'}, {'answer_id': 47445, 'author': 'Daren Thomas', 'author_id': 2260, 'author_profile': 'https://Stackoverflow.com/users/2260', 'pm_score': 2, 'selected': False, 'text': "<p>pushing a string onto a stack and then popping it off - is that still O(1)?\nessentially, that is the same as using split()...</p>\n\n<p>Doesn't O(1) mean in-place? This task gets easy if we can just append strings and stuff, but that uses space...</p>\n\n<p><strong>EDIT</strong>: Thomas Watnedal is right. The following algorithm is O(n) in time and O(1) in space:</p>\n\n<ol>\n<li>reverse string in-place (first iteration over string)</li>\n<li>reverse each (reversed) word in-place (another two iterations over string)\n\n<ol>\n<li>find first word boundary</li>\n<li>reverse inside this word boundary</li>\n<li>repeat for next word until finished</li>\n</ol></li>\n</ol>\n\n<p>I guess we would need to prove that step 2 is really only O(2n)...</p>\n"}, {'answer_id': 47455, 'author': 'John Boker', 'author_id': 2847, 'author_profile': 'https://Stackoverflow.com/users/2847', 'pm_score': 0, 'selected': False, 'text': '<pre><code>using System;\n\nnamespace q47407\n{\n    class MainClass\n    {\n        public static void Main(string[] args)\n        {\n            string s = Console.ReadLine();\n            string[] r = s.Split(\' \');\n            for(int i = r.Length-1 ; i &gt;= 0; i--)\n                Console.Write(r[i] + " ");\n            Console.WriteLine();\n\n        }\n    }\n}\n</code></pre>\n\n<p>edit: i guess i should read the whole question... carry on.</p>\n'}, {'answer_id': 47509, 'author': 'Leon Timmermans', 'author_id': 4727, 'author_profile': 'https://Stackoverflow.com/users/4727', 'pm_score': 2, 'selected': False, 'text': '<pre class="lang-cpp prettyprint-override"><code>#include &lt;string&gt;\n#include &lt;boost/next_prior.hpp&gt;\n\nvoid reverse(std::string&amp; foo) {\n    using namespace std;\n    std::reverse(foo.begin(), foo.end());\n    string::iterator begin = foo.begin();\n    while (1) {\n        string::iterator space = find(begin, foo.end(), \' \');\n        std::reverse(begin, space);\n        begin = boost::next(space);\n        if (space == foo.end())\n            break;\n    }\n}\n</code></pre>\n'}, {'answer_id': 47565, 'author': 'jfs', 'author_id': 4279, 'author_profile': 'https://Stackoverflow.com/users/4279', 'pm_score': 1, 'selected': False, 'text': '<p>@Daren Thomas</p>\n\n<p>Implementation of your algorithm (O(N) in time, O(1) in space) in D (Digital Mars): </p>\n\n<pre><code>#!/usr/bin/dmd -run\n/**\n * to compile &amp; run:\n * $ dmd -run reverse_words.d\n * to optimize:\n * $ dmd -O -inline -release reverse_words.d\n */\nimport std.algorithm: reverse;\nimport std.stdio: writeln;\nimport std.string: find;\n\nvoid reverse_words(char[] str) {\n  // reverse whole string\n  reverse(str);\n\n  // reverse each word\n  for (auto i = 0; (i = find(str, " ")) != -1; str = str[i + 1..length])\n    reverse(str[0..i]);\n\n  // reverse last word\n  reverse(str);\n}\n\nvoid main() {\n  char[] str = cast(char[])("this is a string");\n  writeln(str);\n  reverse_words(str);\n  writeln(str);\n}\n</code></pre>\n\n<p>Output:</p>\n\n<pre>this is a string\nstring a is this</pre>\n'}, {'answer_id': 78071, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': '<p>in Ruby</p>\n\n<blockquote>\n  <blockquote>\n    <p>"this is a string".split.reverse.join(" ")</p>\n  </blockquote>\n</blockquote>\n'}, {'answer_id': 1010975, 'author': 'Demi', 'author_id': 67985, 'author_profile': 'https://Stackoverflow.com/users/67985', 'pm_score': 0, 'selected': False, 'text': '<p>in C#, in-place, O(n), and tested:</p>\n\n<pre class="lang-cs prettyprint-override"><code>static char[] ReverseAllWords(char[] in_text)\n{\n    int lindex = 0;\n    int rindex = in_text.Length - 1;\n    if (rindex &gt; 1)\n    {\n        //reverse complete phrase\n        in_text = ReverseString(in_text, 0, rindex);\n\n        //reverse each word in resultant reversed phrase\n        for (rindex = 0; rindex &lt;= in_text.Length; rindex++)\n        {\n            if (rindex == in_text.Length || in_text[rindex] == \' \')\n            {\n                in_text = ReverseString(in_text, lindex, rindex - 1);\n                lindex = rindex + 1;\n            }\n        }\n    }\n    return in_text;\n}\n\nstatic char[] ReverseString(char[] intext, int lindex, int rindex)\n{\n    char tempc;\n    while (lindex &lt; rindex)\n    {\n        tempc = intext[lindex];\n        intext[lindex++] = intext[rindex];\n        intext[rindex--] = tempc;\n    }\n    return intext;\n}\n</code></pre>\n'}, {'answer_id': 1011107, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>Efficient in terms of my time: took under 2 minutes to write in REBOL:</p>\n\n<pre><code>reverse_words: func [s [string!]] [form reverse parse s none]\n</code></pre>\n\n<p>Try it out:\n    reverse_words  "this is a string"\n    "string a is this"</p>\n'}, {'answer_id': 3337552, 'author': 'Anurag', 'author_id': 165737, 'author_profile': 'https://Stackoverflow.com/users/165737', 'pm_score': 0, 'selected': False, 'text': '<p>A Ruby solution.</p>\n\n<pre class="lang-rb prettyprint-override"><code># Reverse all words in string\ndef reverse_words(string)\n  return string if string == \'\'\n\n  reverse(string, 0, string.size - 1)\n\n  bounds = next_word_bounds(string, 0)\n\n  while bounds.all? { |b| b &lt; string.size }\n    reverse(string, bounds[:from], bounds[:to])\n    bounds = next_word_bounds(string, bounds[:to] + 1)\n  end\n\n  string\nend\n\n# Reverse a single word between indices "from" and "to" in "string"\ndef reverse(s, from, to)\n    half = (from - to) / 2 + 1\n\n    half.times do |i|\n        s[from], s[to] = s[to], s[from]\n        from, to = from.next, to.next\n    end\n\n    s\nend\n\n# Find the boundaries of the next word starting at index "from"\ndef next_word_bounds(s, from)\n  from = s.index(/\\S/, from) || s.size\n  to = s.index(/\\s/, from + 1) || s.size\n\n  return { from: from, to: to - 1 }\nend\n</code></pre>\n'}, {'answer_id': 3711850, 'author': 'Shivkrish22', 'author_id': 401275, 'author_profile': 'https://Stackoverflow.com/users/401275', 'pm_score': 2, 'selected': False, 'text': '<p>Here is my answer. No library calls and no temp data structures.</p>\n\n<pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt;\n\nvoid reverse(char* string, int length){\n    int i;\n    for (i = 0; i &lt; length/2; i++){\n        string[length - 1 - i] ^= string[i] ;\n        string[i] ^= string[length - 1 - i];\n        string[length - 1 - i] ^= string[i];\n    }   \n}\n\nint main () {\nchar string[] = "This is a test string";\nchar *ptr;\nint i = 0;\nint word = 0;\nptr = (char *)&amp;string;\nprintf("%s\\n", string);\nint length=0;\nwhile (*ptr++){\n    ++length;\n}\nreverse(string, length);\nprintf("%s\\n", string);\n\nfor (i=0;i&lt;length;i++){\n    if(string[i] == \' \'){\n       reverse(&amp;string[word], i-word);\n       word = i+1;\n       }\n}   \nreverse(&amp;string[word], i-word); //for last word             \nprintf("\\n%s\\n", string);\nreturn 0;\n}\n</code></pre>\n'}, {'answer_id': 23667400, 'author': 'vran freelancer', 'author_id': 1092823, 'author_profile': 'https://Stackoverflow.com/users/1092823', 'pm_score': 0, 'selected': False, 'text': "<p>This problem can be solved with O(n) in time and O(1) in space. The sample code looks as mentioned below:</p>\n\n<pre><code>    public static string reverseWords(String s)\n    {\n\n        char[] stringChar = s.ToCharArray();\n        int length = stringChar.Length, tempIndex = 0;\n\n        Swap(stringChar, 0, length - 1);\n\n        for (int i = 0; i &lt; length; i++)\n        {\n            if (i == length-1)\n            {\n                Swap(stringChar, tempIndex, i);\n                tempIndex = i + 1;\n            }\n            else if (stringChar[i] == ' ')\n            {\n                Swap(stringChar, tempIndex, i-1);\n                tempIndex = i + 1;\n            }\n        }\n\n        return new String(stringChar);\n    }\n\n    private static void Swap(char[] p, int startIndex, int endIndex)\n    {\n        while (startIndex &lt; endIndex)\n        {\n            p[startIndex] ^= p[endIndex];\n            p[endIndex] ^= p[startIndex];\n            p[startIndex] ^= p[endIndex];\n            startIndex++;\n            endIndex--;\n        }\n    }\n</code></pre>\n"}, {'answer_id': 27279070, 'author': 'aady', 'author_id': 2047752, 'author_profile': 'https://Stackoverflow.com/users/2047752', 'pm_score': 0, 'selected': False, 'text': '<p>A one liner:</p>\n\n<pre><code>l="Is this as expected ??"\n" ".join(each[::-1] for each in l[::-1].split())\n</code></pre>\n\n<p>Output:</p>\n\n<pre><code>\'?? expected as this Is\'\n</code></pre>\n'}, {'answer_id': 27602891, 'author': 'zoha khan', 'author_id': 3209871, 'author_profile': 'https://Stackoverflow.com/users/3209871', 'pm_score': 0, 'selected': False, 'text': '<blockquote>\n  <p>Algorithm:\n  1).Reverse each word of the string.\n  2).Reverse resultant String.</p>\n</blockquote>\n\n<pre><code>public class Solution {\npublic String reverseWords(String p) {\n   String reg=" ";\n  if(p==null||p.length()==0||p.equals(""))\n{\n    return "";\n}\nString[] a=p.split("\\\\s+");\nStringBuilder res=new StringBuilder();;\nfor(int i=0;i&lt;a.length;i++)\n{\n\n    String temp=doReverseString(a[i]);\n    res.append(temp);\n    res.append(" ");\n}\nString resultant=doReverseString(res.toString());\nSystem.out.println(res);\nreturn resultant.toString().replaceAll("^\\\\s+|\\\\s+$", ""); \n}\n\n\npublic String doReverseString(String s)`{`\n\n\nchar str[]=s.toCharArray();\nint start=0,end=s.length()-1;\nwhile(start&lt;end)\n{\nchar temp=str[start];\nstr[start]=str[end];\nstr[end]=temp;\nstart++;\nend--;\n}\nString a=new String(str);\nreturn a;\n\n}\n\npublic static void main(String[] args)\n{\nSolution r=new Solution();\nString main=r.reverseWords("kya hua");\n//System.out.println(re);\nSystem.out.println(main);\n}\n}\n</code></pre>\n'}, {'answer_id': 37529508, 'author': 'Himanshu Mahajan', 'author_id': 1624283, 'author_profile': 'https://Stackoverflow.com/users/1624283', 'pm_score': 0, 'selected': False, 'text': '<p>The algorithm to solve this problem is based on two steps process, first step will reverse the individual words of string,then in second step, reverse whole string. Implementation of algorithm will take O(n) time and O(1) space complexity.</p>\n\n<pre><code>      #include &lt;stdio.h&gt;\n      #include &lt;string.h&gt;\n\n      void reverseStr(char* s, int start, int end);\n\n      int main()\n      {\n              char s[] = "This is test string";\n\n              int start = 0;\n              int end = 0;\n              int i = 0;\n\n              while (1) {\n\n              if (s[i] == \' \' || s[i] == \'\\0\')\n              {\n                    reverseStr(s, start, end-1);\n                    start = i + 1;\n                    end = start;\n              }\n              else{\n                    end++;\n              }\n\n              if(s[i] == \'\\0\'){\n                   break;\n              }\n              i++;\n      }\n\n      reverseStr(s, 0, strlen(s)-1);\n      printf("\\n\\noutput= %s\\n\\n", s);\n\n      return 0;\n  }\n\n  void reverseStr(char* s, int start, int end)\n  {\n     char temp;\n     int j = end;\n     int i = start;\n\n     for (i = start; i &lt; j ; i++, j--) {\n          temp = s[i];\n          s[i] = s[j];\n          s[j] = temp;\n     }\n }\n</code></pre>\n'}, {'answer_id': 37877392, 'author': 'Sundara Moorthy Anandh', 'author_id': 6477821, 'author_profile': 'https://Stackoverflow.com/users/6477821', 'pm_score': 1, 'selected': False, 'text': '<blockquote>\n  <p><strong><em>THIS PROGRAM IS TO REVERSE THE SENTENCE USING POINTERS IN "C language" By Vasantha kumar &amp; Sundaramoorthy from KONGU ENGG COLLEGE, Erode.</em></strong></p>\n</blockquote>\n\n<p><strong>NOTE</strong>:   Sentence must end with <strong>dot(.)</strong>\n because NULL character is not assigned automatically\n at the end of the sentence*</p>\n\n<pre><code> #include&lt;stdio.h&gt;\n #include&lt;string.h&gt;\n\nint main()\n{\nchar *p,*s="this is good.",*t;\nint i,j,a,l,count=0;\n\nl=strlen(s);\n\np=&amp;s[l-1];\n\nt=&amp;s[-1];\nwhile(*t)\n   {\n      if(*t==\' \')\n     count++;\n     t++;\n   }\n   a=count;\n  while(l!=0)\n   {\nfor(i=0;*p!=\' \'&amp;&amp;t!=p;p--,i++);\n   p++;\n\n  for(;((*p)!=\'.\')&amp;&amp;(*p!=\' \');p++)\n    printf("%c",*p);\n  printf(" ");\n  if(a==count)\n   {\n     p=p-i-1;\n     l=l-i;\n   }\n  else\n   {\n     p=p-i-2;\n     l=l-i-1;\n   }\n\ncount--;\n  }\n\nreturn 0;  \n}\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/47402', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/4279/']