strings/reverse_string_words.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem\n",
    "\n",
    "Given a string of words delimited by spaces, reverse the words in string. For example, given \"hello world here\", return \"here world hello\"\n",
    "\n",
    "Follow-up: given a mutable string representation, can you perform this operation in-place?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Approach \n",
    "\n",
    "Since strings are immutable, a mutable string can be represented as a list of characters in a buffer e.g  `['h','e','l','l','o',' ','w','o','r','l','d']` == 'hello world'\n",
    "\n",
    "First we reverse entire string to get `'dlrow olleh'`, then we reverse each word within the string to obtain original words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse(string_list: list, start: int, end: int) -> str:\n",
    "    while start < end:\n",
    "        string_list[start], string_list[end] = string_list[end], string_list[start]\n",
    "        start += 1\n",
    "        end -= 1\n",
    "\n",
    "def reverse_words(string_list: list) -> str:\n",
    "    reverse(string_list, 0, len(string_list) - 1)\n",
    "    start = 0\n",
    "    for i in range(len(string_list)):\n",
    "        if string_list[i] == \" \":\n",
    "            reverse(string_list, start, i - 1)\n",
    "            start = i + 1\n",
    "    # we need to reverse the last sub-string\n",
    "    reverse(string_list, start, len(string_list) - 1)\n",
    "    return \"\".join(string_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'there hello well'"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "string_list = list(\"well hello there\")\n",
    "reverse_words(string_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}