Python_DP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "wooden-india",
   "metadata": {},
   "source": [
    "# Dynamic Programming notebook\n",
    "\n",
    "### 1. Fibonacci \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "complimentary-timer",
   "metadata": {},
   "outputs": [],
   "source": [
    "# The fibo sequence \n",
    "def fib(n):\n",
    "    if (n<= 2):return 1\n",
    "    return fib(n-1) + fib(n-2)\n",
    "#T = O(2^n)\n",
    "#S = O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "paperback-philadelphia",
   "metadata": {},
   "source": [
    "#### ●Memoization "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "coral-shelf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now using dynamic programming approach \n",
    "# memoization \n",
    "def fib(n, mem = {}): # store all the previously found sub solution into a memory or in hash table.\n",
    "    if (n in mem) : return mem[n]  # if in that memo return else compute untill it hits the base case.\n",
    "    if n<=2 : return 1\n",
    "    mem[n] =  fib(n-1, mem) + fib(n-2, mem)\n",
    "\n",
    "    return mem[n]\n",
    "#T = O(n)\n",
    "#S = O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "becoming-island",
   "metadata": {},
   "source": [
    "#### ●Tabulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "australian-turning",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    a, b = 0,1\n",
    "    for _ in range(n-1):\n",
    "        c = a + b\n",
    "        a = b\n",
    "        b = c\n",
    "    return b\n",
    "# t = O(N)\n",
    "# s = O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "corporate-jonathan",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    list = [0]*(n+1)  # Construct a table and init with some deafult vlaues\n",
    "    list[1] = 1   # Seed value\n",
    "    \n",
    "    for i in range(1,n):\n",
    "        list[i+1] += list[i] + list[i-1]\n",
    "    return list[n]\n",
    "# t = O(N*M)\n",
    "# s = O(M)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "administrative-gross",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "centered-minutes",
   "metadata": {},
   "source": [
    "### 2.  Grid Travller Problem \n",
    "#### ●Brute Force "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 448,
   "id": "motivated-organic",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gridTravaller(n,m):\n",
    "    if (n == 1 and  m == 1): return 1\n",
    "    if (n == 0 or   m == 0): return 0\n",
    "    return gridTravaller(n-1,m) + gridTravaller(n, m-1)\n",
    "# t = O(2^n+m)\n",
    "# s = O(N)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "relevant-chain",
   "metadata": {},
   "source": [
    "#### ●Memoization "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 449,
   "id": "champion-sense",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using the dp approch \n",
    "# using memoization \n",
    "def gridTravaller(n,m, mem = {}):\n",
    "    key = f'{m},{n}'\n",
    "    for key in mem : return mem[key]\n",
    "    if (n == 1 and  m == 1): return 1\n",
    "    if (n == 0 or   m == 0): return 0\n",
    "    mem[key] = gridTravaller(n-1,m, mem) + gridTravaller(n, m-1, mem)\n",
    "    return mem[key]\n",
    "# t = O(2^n+m)\n",
    "# s = O(N)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "banned-absence",
   "metadata": {},
   "source": [
    "#### ●Tabulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 450,
   "id": "complex-preservation",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gridTravaller(m,n):\n",
    "    matrix = [0]*(m+1)\n",
    "    matrix = [[0]*(n+1) for i in matrix]   # create a MxN table and init it with some defualt value\n",
    "    matrix[1][1] = 1                       # Seed value, trivial subproblem 1x1 is always 1  \n",
    "    for i in range(m+1):                   # Iteration and logic\n",
    "        for j in range(n+1):\n",
    "            current = matrix[i][j]\n",
    "            if j+1 <= n: matrix[i][j+1] += current\n",
    "            if i+1 <= m: matrix[i+1][j] += current\n",
    "    return matrix[i][j]\n",
    "# t = O(m*n)\n",
    "# s = O(m*n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 451,
   "id": "imperial-blake",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2333606220"
      ]
     },
     "execution_count": 451,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gridTravaller(18,18)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "surprised-design",
   "metadata": {},
   "source": [
    "### 3.1. CanSum Problem \n",
    "#### ●Brute Force"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "id": "disturbed-procedure",
   "metadata": {},
   "outputs": [],
   "source": [
    "def canSum(targetSum, llist):\n",
    "    # base cases +ve\n",
    "    if targetSum == 0: return True\n",
    "    if targetSum <  0: return False \n",
    "    \n",
    "    for ts in llist:\n",
    "        rem = targetSum - ts\n",
    "        if(canSum(rem, llist)): return True\n",
    "    return False\n",
    "# t = O(n^m)\n",
    "# s = O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "disturbed-stuart",
   "metadata": {},
   "source": [
    "#### ●Memoization "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "alpha-wednesday",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using the dp approch \n",
    "# using memoization \n",
    "def canSum(targetSum, llist, mem = {}):\n",
    "    # base cases +ve\n",
    "    key = targetSum\n",
    "    if key in mem: return mem[key]\n",
    "    if targetSum == 0: return True\n",
    "    if targetSum <  0: return False \n",
    "    \n",
    "    for num in llist:         \n",
    "        if(canSum(targetSum - num, llist)): \n",
    "            mem[key] = True\n",
    "            return mem[key]\n",
    "    else:\n",
    "        mem[key] = False\n",
    "        return mem[key] \n",
    "# t = O(n)\n",
    "# s = O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "practical-aquarium",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "canSum(300,[7,14])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "informal-shore",
   "metadata": {},
   "source": [
    "#### ●Tabulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 452,
   "id": "rapid-ocean",
   "metadata": {},
   "outputs": [],
   "source": [
    "def canSum(targetSum, llist):\n",
    "    table = [False] * (targetSum + 1)# Create a table of (targetSum length + 1) and init with some default vlaue based on the return vlaue \n",
    "    table[0] = True  # Seed valu by making trival sub problem. Given any array it is possible to generate 0\n",
    "    \n",
    "    for i in range(targetSum +1):  # iteration and the logic \n",
    "        if(table[i]):\n",
    "            for j in llist:\n",
    "                if (i+j) <= targetSum : table[i+j] = True\n",
    "\n",
    "    return table[targetSum]\n",
    "# t = O(n*m)\n",
    "# s = O(m)           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 453,
   "id": "representative-county",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 453,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "canSum(7,[5,4,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "varied-anderson",
   "metadata": {},
   "source": [
    "### 3.2 HowSum Problem\n",
    "#### ●Brute Force"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "greatest-therapy",
   "metadata": {},
   "outputs": [],
   "source": [
    "def howSum(targetSum, numbers):\n",
    "    #base case \n",
    "    if targetSum == 0: return []\n",
    "    if targetSum <  0: return None\n",
    "    \n",
    "    for num in numbers:  # iterate through the numbers in the array for possible matches \n",
    "        result = howSum(targetSum - num, numbers)\n",
    "        if result != None:\n",
    "            return [ *result, num]\n",
    "    return None\n",
    "# time complexity = O(n**m * m)\n",
    "# space = O(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "id": "protective-consistency",
   "metadata": {},
   "outputs": [],
   "source": [
    "howSum(300,[7,14])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "utility-queue",
   "metadata": {},
   "source": [
    "#### ●Memoization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "id": "israeli-committee",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using the dp approch \n",
    "# using memoization \n",
    "def howSum(targetSum, numbers, mem = {}):\n",
    "    if targetSum in mem: return mem[targetSum]\n",
    "    #base case \n",
    "    if targetSum == 0: return []\n",
    "    if targetSum <  0: return None\n",
    "    \n",
    "    for num in numbers:  # iterate through the numbers in the array for possible matches \n",
    "        result = howSum(targetSum - num, numbers)\n",
    "        if result != None:\n",
    "            mem[targetSum] = [ *result, num]\n",
    "            return mem[targetSum]\n",
    "    mem[targetSum] = None\n",
    "    return mem[targetSum]\n",
    "# time complexity = O(n*m**2)\n",
    "# space = O(m**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "organizational-pricing",
   "metadata": {},
   "source": [
    "#### ●Tabulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 388,
   "id": "forced-backing",
   "metadata": {},
   "outputs": [],
   "source": [
    "def howSum(targetSum, llist):\n",
    "    table = [None] * (targetSum + 1)# Create a table of (targetSum length + 1) and init with some default vlaue based on the return vlaue \n",
    "    table[0] = []  # Seed valu by making trival sub problem. Given any array it is possible to generate 0\n",
    "    \n",
    "    for i in range(targetSum +1):  # iteration and the logic \n",
    "        if(table[i] is not None):\n",
    "            for j in llist:\n",
    "                if (i+j) <= targetSum : table[i+j] = [*table[i],j]\n",
    "         \n",
    "    return table[targetSum]   #filter out the none in the final answer\n",
    "# t = O(n*m**2)\n",
    "# s = O(m**2)           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 391,
   "id": "stunning-hampton",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 2, 2]"
      ]
     },
     "execution_count": 391,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "howSum(8,[5,3,2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "altered-second",
   "metadata": {},
   "source": [
    "### 3.3 BestSum Problem \n",
    "#### ●Brute Force"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "verified-grass",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bestSum(targetSum, numbers):\n",
    "    #base case \n",
    "    if targetSum == 0: return []\n",
    "    if targetSum <  0: return None\n",
    "    \n",
    "    shortestCombination = None\n",
    "    \n",
    "    for num in numbers:  # iterate through the numbers in the array for possible matches \n",
    "        result = bestSum(targetSum - num, numbers)\n",
    "        if result != None:\n",
    "            currentCombination =  [ *result, num]\n",
    "            if ( shortestCombination == None or len(currentCombination) < len(shortestCombination)):\n",
    "                shortestCombination = currentCombination\n",
    "                \n",
    "    return shortestCombination\n",
    "# time complexity = O(n**m * m)\n",
    "# space = O(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "coastal-diagram",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[25, 25, 25, 25]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bestSum(100,[1,2,5,25])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "mechanical-limitation",
   "metadata": {},
   "source": [
    "#### ●Memoization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "whole-gothic",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bestSum(targetSum, numbers, mem = {}):\n",
    "    #base case \n",
    "    if targetSum in mem: return mem[targetSum]\n",
    "    if targetSum == 0: return []\n",
    "    if targetSum <  0: return None\n",
    "    \n",
    "    shortestCombination = None\n",
    "    \n",
    "    for num in numbers:  # iterate through the numbers in the array for possible matches \n",
    "        result = bestSum(targetSum - num, numbers)\n",
    "        if result != None:\n",
    "            currentCombination =  [ *result, num]\n",
    "            if ( shortestCombination == None or len(currentCombination) < len(shortestCombination)):\n",
    "                shortestCombination = currentCombination\n",
    "    mem[targetSum] = shortestCombination\n",
    "    return mem[targetSum]\n",
    "# time complexity = O(n**m * m)\n",
    "# space = O(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 269,
   "id": "macro-clothing",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Or, \n",
    "# Using the dp approch \n",
    "# using memoization \n",
    "def bestSum(targetSum, numbers, mem = {}):\n",
    "    #base case \n",
    "    if targetSum in mem: return mem[targetSum]\n",
    "    if targetSum == 0: return []\n",
    "    if targetSum <  0: return None\n",
    "    \n",
    "    mem[targetSum] = None\n",
    "    \n",
    "    for num in numbers:  # iterate through the numbers in the array for possible matches \n",
    "        result = bestSum(targetSum - num, numbers, mem)\n",
    "        if result != None:\n",
    "            currentCombination =  [ *result, num]\n",
    "            if ( mem[targetSum] == None or len(currentCombination) < len(mem[targetSum])):\n",
    "                mem[targetSum] = currentCombination\n",
    "                \n",
    "    return mem[targetSum]\n",
    "# time complexity = O(n**m * m)\n",
    "# space = O(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "gorgeous-april",
   "metadata": {},
   "source": [
    "#### ●Tabulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "substantial-uniform",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bestSum(targetSum, llist):\n",
    "    table = [None] * (targetSum + 1)# Create a table of (targetSum length + 1) and init with some default vlaue based on the return vlaue \n",
    "    table[0] = []  # Seed values by making trival sub problem. Given any array it is possible to generate 0\n",
    "    \n",
    "    for i in range(targetSum +1):  # iteration and the logic \n",
    "        if(table[i] is not None):\n",
    "            for j in llist:\n",
    "                if (i+j) <= targetSum : \n",
    "                    current = table[i] + [j]\n",
    "                    if table[i+j] is None or (len(table[i+j]) > len(current)): table[i+j] = current\n",
    "    return table[targetSum]   #filter out the none in the final answer\n",
    "# t = O(n*m**2)\n",
    "# s = O(m**2)           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "dense-norway",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8]"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bestSum(8,[7,8,3,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "spare-electric",
   "metadata": {},
   "source": [
    "### 4.1 CanConstruct Problem \n",
    "#### ●Brute Force"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "substantial-timeline",
   "metadata": {},
   "outputs": [],
   "source": [
    "def canConstruct(target, wordBank):\n",
    "    #base case \n",
    "    if target == '': return True \n",
    "    \n",
    "    for word in wordBank:\n",
    "        try:\n",
    "        \n",
    "            if target.index(word) == 0:          # ie. check whether the sub-string is present in the target string\n",
    "                                                 # And, importantly make sure that it is a prefix only.(From the tree diagram)\n",
    "                    sufix = target[len(word):]    # List slicing, slice the prefix from the list so that,\n",
    "                                                 #next substring is the prefix for futre recurssion\n",
    "                    if(canConstruct(sufix,wordBank) == True):\n",
    "                        return True\n",
    "        except:None\n",
    "                \n",
    "    return False\n",
    "            \n",
    "# time complexity = O(n**m * m)\n",
    "# space = O(m**2)        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "magnetic-absolute",
   "metadata": {},
   "source": [
    "#### ●Memoization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "electrical-treat",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using the dp approch \n",
    "# using memoization \n",
    "def canConstruct(target, wordBank, mem = {}):\n",
    "    #base case \n",
    "    if target in mem: return mem[target]\n",
    "    if target == '': return True \n",
    "    \n",
    "    for word in wordBank:\n",
    "        try:\n",
    "        \n",
    "            if target.index(word) == 0:          # ie. check whether the sub-string is present in the target string\n",
    "                                                 # And, importantly make sure that it is a prefix only.(From the tree diagram)\n",
    "                    sufix = target[len(word):]    # List slicing, slice the prefix from the list so that,\n",
    "                                                 #next substring is the prefix for futre recurssion\n",
    "                    if(canConstruct(sufix,wordBank, mem) == True):\n",
    "                        mem[target] = True\n",
    "                        return mem[target]\n",
    "        except:None\n",
    "    mem[target] = False\n",
    "    return mem[target]\n",
    "            \n",
    "# time complexity = O(n*m*m) =>(m**2*n)\n",
    "# space = O(m**2)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "specific-minister",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "canConstruct(\"abcd\",[\"abcd\",\"ab\"])\n",
    "#canConstruct(\"skateboard\", [\"bo\", \"rd\", \"ate\", \"t\", \"sk\", \"boat\"])\n",
    "canConstruct(\"eeeeeeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\",\"eee\",\"eeeeeeeeee\",\"eeeeeeeeeeee\",\"e\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "signal-subscription",
   "metadata": {},
   "source": [
    "#### ●Tabulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "id": "deluxe-projector",
   "metadata": {},
   "outputs": [],
   "source": [
    "def canConstruct(target, wordBank):\n",
    "    table = [False] * (len(target) + 1)   # Create a table of (targetSum length + 1) and init with some default vlaue based on the return vlaue \n",
    "    table[0] = True # Seed values by making trival sub problem. Given any array it is possible to generate 0\n",
    "    \n",
    "    for i in range(len(target)):  # iteration and logic\n",
    "        if table[i] == True:\n",
    "            for word in wordBank:\n",
    "                if (word == target[i: i + len(word)]):\n",
    "                    table[i+len(word)] = True\n",
    "\n",
    "    return table[len(target)]\n",
    "# time complexity = O(n*m*m)\n",
    "# space = O(m)                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "id": "latin-questionnaire",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "canConstruct(\"eeeeeeeeeeeeeeeeeeeeeeeeeeeeef\", [\"eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef\",\"e\",\"\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "informational-sentence",
   "metadata": {},
   "source": [
    "### 4.2 CountConstruct Problem\n",
    "#### ●Brute Force"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "occasional-copyright",
   "metadata": {},
   "outputs": [],
   "source": [
    "def countConstruct(target, wordBank):\n",
    "    #base case \n",
    "    if target == '': return 1\n",
    "    totalCounter = 0\n",
    "    for word in wordBank:\n",
    "        try:\n",
    "        \n",
    "            if target.index(word) == 0:          # ie. check whether the sub-string is present in the target string\n",
    "                                                 # And, importantly make sure that it is a prefix only.(From the tree diagram)\n",
    "                    sufix = target[len(word):]    # List slicing, slice the prefix from the list so that,\n",
    "                                                 #next substring is the prefix for futre recurssion\n",
    "                    counter = countConstruct(sufix,wordBank)\n",
    "                    totalCounter += counter\n",
    "                    \n",
    "        except:None\n",
    "                \n",
    "    return totalCounter\n",
    "            \n",
    "# time complexity = O(n**m * m)\n",
    "# space = O(m**2)        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sought-watch",
   "metadata": {},
   "source": [
    "#### ●Memoization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "unsigned-moses",
   "metadata": {},
   "outputs": [],
   "source": [
    "def countConstruct(target, wordBank, mem = {}):\n",
    "    #base case \n",
    "    if target in mem: return mem[target]\n",
    "    if target == '': return 1\n",
    "    totalCounter = 0\n",
    "    for word in wordBank:\n",
    "        try:\n",
    "        \n",
    "            if target.index(word) == 0:          # ie. check whether the sub-string is present in the target string\n",
    "                                                 # And, importantly make sure that it is a prefix only.(From the tree diagram)\n",
    "                    sufix = target[len(word):]    # List slicing, slice the prefix from the list so that,\n",
    "                                                 #next substring is the prefix for futre recurssion\n",
    "                    counter = countConstruct(sufix,wordBank, mem)\n",
    "                    totalCounter += counter\n",
    "            \n",
    "        except:None\n",
    "            \n",
    "    mem[target] = totalCounter\n",
    "    return totalCounter \n",
    "            \n",
    "# time complexity = O(n**m * m)\n",
    "# space = O(m**2)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "copyrighted-peninsula",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countConstruct(\"purple\", [\"purp\", \"p\", \"ur\", \"le\", \"purpl\"])\n",
    "countConstruct(\"eeeeeeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\",\"eee\",\"eeeeeeeeee\",\"eeeeeeeeeeee\",\"e\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "recovered-solution",
   "metadata": {},
   "source": [
    "#### ●Tabulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "id": "dimensional-bermuda",
   "metadata": {},
   "outputs": [],
   "source": [
    "def countConstruct(target, wordBank):\n",
    "    table = [0] * (len(target) + 1)   # Create a table of (targetSum length + 1) and init with some default vlaue based on the return vlaue \n",
    "    table[0] = 1 # Seed values by making trival sub problem. Given any array it is possible to generate 0\n",
    "    \n",
    "    \n",
    "    for i in range(len(target)):  # iteration and logic\n",
    "        if table[i]:\n",
    "            for word in wordBank:\n",
    "                if (word == target[i: i + len(word)]):\n",
    "                    table[i+len(word)] += table[i] \n",
    "     \n",
    "    return table[len(target)]\n",
    "# time complexity = O(n*m*m)\n",
    "# space = O(m)             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "id": "complex-buddy",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 197,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countConstruct(\"purple\", [\"purp\", \"p\", \"ur\", \"le\", \"purpl\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "growing-split",
   "metadata": {},
   "source": [
    "### 4.3 AllConstruct Problem\n",
    "#### ●Brute Force"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 317,
   "id": "bulgarian-archives",
   "metadata": {},
   "outputs": [],
   "source": [
    "def allConstruct(target, wordBank):\n",
    "    #base cases\n",
    "    if target == \"\" : return [[]]\n",
    "    allWays = []\n",
    "    for word in wordBank:\n",
    "        try:\n",
    "            if(target.index(word) == 0):\n",
    "                suffix = target[len(word):]\n",
    "                suffixWay = allConstruct(suffix, wordBank)   # returns the solution from one of the child node\n",
    "                totalWay = [[word] + way for way in suffixWay]                  # pushes the array (solution) with the parent node to form a sub solution of that parent target \n",
    "                if totalWay:\n",
    "                    allWays.extend(totalWay)            # pushes the sub-solution to the root and obtain one of the ways\n",
    "                \n",
    "        except:None\n",
    "    return allWays"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "satisfactory-placement",
   "metadata": {},
   "source": [
    "#### ●Memoization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "fifteen-continent",
   "metadata": {},
   "outputs": [],
   "source": [
    "def allConstruct(target, wordBank, mem={}):\n",
    "    #base cases\n",
    "    if target in mem: return mem[target]\n",
    "    if target == \"\" : return [[]]\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for word in wordBank:\n",
    "        try:\n",
    "            if(target.index(word) == 0):\n",
    "                suffix = target[len(word):]\n",
    "                suffixWay = allConstruct(suffix, wordBank, mem)   # returns the solution from one of the child node\n",
    "                totalWay = [[word] + way for way in suffixWay]                  # pushes the array (solution) with the parent node to form a sub solution of that parent target \n",
    "                result.extend(totalWay)            # pushes the sub-solution to the root and obtain one of the ways\n",
    "                \n",
    "        except:None\n",
    "    mem[target] = result\n",
    "    return mem[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "blocked-comment",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "allConstruct(\"eeeeeeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\",\"eee\",\"eeeeeeeeee\",\"eeeeeeeeeeee\",\"e\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "christian-oliver",
   "metadata": {},
   "source": [
    "#### ●Tabulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "metropolitan-strap",
   "metadata": {},
   "outputs": [],
   "source": [
    "def allConstruct(target, wordBank):\n",
    "    #table = [[]]* (len(target) + 1) # do not use this, this is a trap. Just map it using a for loop, this only creates the illusion that it has created list of empty list.\n",
    "    table = [[] for _ in range(len(target) + 1)]# Create a table of (targetSum length + 1) and init with some default vlaue based on the return vlaue \n",
    "    table[0] = [[]] # Seed values by making trival sub problem. Given any array it is possible to generate 0\n",
    "    \n",
    "    for i in range(len(target)):\n",
    "        for word in wordBank:\n",
    "            if(target[i: i + len(word)] == word): \n",
    "                newCombination = [ prevCombination + [word] for prevCombination in table[i]] # take the (combination present in the current cell) along with the current word\n",
    "                table[i + len(word)].extend(newCombination) # Push the new combination to the new target\n",
    "    return table[-1]\n",
    "# time complexity = O(n*m**m)\n",
    "# space = O(m**m) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "attempted-property",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['purp', 'le'], ['p', 'ur', 'p', 'le']]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "allConstruct(\"purple\", [\"purp\", \"p\", \"ur\", \"le\", \"purpl\"])"
   ]
  }
 ],
 "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}