{"id":3703,"date":"2021-11-12T17:28:39","date_gmt":"2021-11-12T11:58:39","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3703"},"modified":"2021-11-12T17:28:40","modified_gmt":"2021-11-12T11:58:40","slug":"reverse-words-in-a-string","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/reverse-words-in-a-string\/","title":{"rendered":"Reverse Words in a String"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#sample-test-cases\">Sample Test Cases<\/a><\/li><li><a href=\"#approach\">Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#optimal-approach\">Optimal Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a <strong>sentence <\/strong>of the form of words separated by spaces, return a new sentence that consists of the words of the original sentence in the reverse order.<\/p>\n\n\n\n<h2 id=\"sample-test-cases\">Sample Test Cases<\/h2>\n\n\n\n<p>Input 1:<\/p>\n\n\n\n<p>s = \u201cHello World\u201d<\/p>\n\n\n\n<p>Output 1:<\/p>\n\n\n\n<p>World Hello<\/p>\n\n\n\n<p>Input 2:<\/p>\n\n\n\n<p>s = \u201cThis is a good day\u201d<\/p>\n\n\n\n<p>Output 2:<\/p>\n\n\n\n<p>day good a is This<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<h3 id=\"naive-approach\">Naive Approach<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"552\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"naive approach\"  class=\"wp-image-3783 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach-1024x552.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach-1024x552.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach-300x162.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach-768x414.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach-380x205.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach-550x297.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach-800x431.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach-1160x625.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/naive-approach.png 1354w\" ><\/figure>\n\n\n\n<p>The naive approach for this problem is to <strong>split<\/strong> the string into individual words using the <strong>spaces<\/strong> as delimiters, and then print the words in reverse order.<\/p>\n\n\n\n<p><strong>Code \/ Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">string reverseStringByWords(string s) {\n  vector &lt; string > words;\n  string word = \"\";\n  for (char c: s) {\n    if (c == ' ') {\n      words.push_back(word);\n      word = \"\";\n    } else {\n      word += c;\n    }\n  }\n  words.push_back(word);\n  string ans = \"\";\n  reverse(words.begin(), words.end());\n  for (auto x: words) {\n    ans += x;\n    ans += \" \";\n  }\n  return ans;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static void reverse(char[] ch, int left, int right) {\n  while (left &lt;= right) {\n    char temp = ch[right];\n    ch[right] = ch[left];\n    ch[left] = temp;\n    left++;\n    right--;\n  }\n}\npublic static String reverseByWords(String s) {\n  char[] ch = s.toCharArray();\n  int beg = 0;\n  for (int i = 0; i &lt; ch.length; i++) {\n    if (ch[i] == ' ') {\n      reverse(ch, beg, i);\n      beg = i + 1;\n    }\n  }\n  reverse(ch, beg, ch.length - 1);\n  reverse(ch, 0, ch.length - 1);\n  String ans = Arrays.toString(ch);\n  return ans;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def reverse(s, left, right):\n    while left &lt;= right:\n        s[left], s[right] = s[right], s[left]\n        left += 1\n        right -= 1\n\n\ndef reverseByWords(s):\n    s = list(s)\n    n = len(s)\n    beg = 0\n    for i in range(n):\n        if s[i] == \" \":\n            reverse(s, beg, i - 1)\n            beg = i + 1\n    reverse(s, beg, n - 1)\n    reverse(s, 0, n - 1)\n    s = \"\".join(s)\n    return s<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n)<\/li><li>Space Complexity: O(n)<\/li><\/ul>\n\n\n\n<h2 id=\"optimal-approach\">Optimal Approach<\/h2>\n\n\n\n<p>The optimal approach tries to swap the words of the string from the beginning and end, using a <strong>two-pointers-based<\/strong> approach, to reverse the string in <strong>constant space<\/strong>. The algorithm is as follows:<\/p>\n\n\n\n<ul><li>Convert the string into an array of strings, which will store the words.<\/li><li>Initialize the 2 pointers <strong>left<\/strong> and <strong>right<\/strong> to <strong>0<\/strong> and <strong>string.length() &#8211; 1<\/strong> respectively.<\/li><li>While the <strong>left<\/strong> pointer does not exceed the <strong>right<\/strong> pointer, swap the elements at the <strong>left<\/strong> and <strong>right<\/strong> pointer, move the <strong>left<\/strong> pointer forward and the <strong>right<\/strong> pointer backward by <strong>1<\/strong> place.<\/li><li>Finally, return the final calculated string.<\/li><\/ul>\n\n\n\n<p><strong>Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">string reverseByWords(string s) {\n  vector &lt; string > words;\n  string str = \"\";\n  for (char c: s) {\n    if (c == ' ') {\n      words.push_back(str);\n      str = \"\";\n    } else {\n      str += c;\n    }\n  }\n  words.push_back(str);\n  int left = 0, right = words.size() - 1;\n  while (left &lt;= right) {\n    swap(words[left], words[right]);\n    left++;\n    right--;\n  }\n  string ans = \"\";\n  for (auto x: words) {\n    ans += x;\n    ans += \" \";\n  }\n  ans.pop_back();\n  return ans;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static String reverseByWords(String s) {\n  String[] words = s.split(\"\\\\s\");\n  int left = 0, right = words.length - 1;\n  while (left &lt;= right) {\n    String temp = words[left];\n    words[left] = words[right];\n    words[right] = temp;\n    left += 1;\n    right -= 1;\n  }\n  String ans = String.join(\" \", words);\n  return ans;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def reverseByWords(s):\n    s = s.split(\" \")\n    left = 0\n    right = len(s) - 1\n    while left &lt;= right:\n        s[left], s[right] = s[right], s[left]\n        left += 1\n        right -= 1\n    s = \" \".join(s)\n    return s<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n)<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<p><strong>Practice Problem:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/old\/problems\/reverse-the-string\/\" target=\"_blank\" rel=\"noreferrer noopener\">Reverse the String<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>1. When a problem is asked to be solved in constant space, what should be the thought process?<\/strong><\/p>\n\n\n\n<p>A. While the idea may vary from problem to problem, <strong>swapping<\/strong> is a very common method used in problems requiring to be solved in constant space.<\/p>\n\n\n\n<p><strong>2. What is the time complexity of the swap function in C++?<\/strong><\/p>\n\n\n\n<p>A. The swap function in C++ works in O(1) time complexity.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a sentence of the form of words separated by spaces, return a new sentence that&hellip;\n","protected":false},"author":5,"featured_media":3782,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[566],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3703"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3703"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3703\/revisions"}],"predecessor-version":[{"id":22727,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3703\/revisions\/22727"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3782"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3703"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3703"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3703"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}