Dynamic Programming/LongestCommonSubsequence.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "LongestCommonSubsequence.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "a3hYgaHPUkua"
      },
      "source": [
        "'''\n",
        "  Function to find Longest Common Subsequence of 2 lists of string\n",
        "  Time complexity = O(|L1|.|L2|), |L| is length of string list\n",
        "\n",
        "  Parameters:\n",
        "  -----------\n",
        "    strList1: list\n",
        "              The first input string list \n",
        "    strList2: list\n",
        "              The second input string list  \n",
        "    output  : 'stringList' (default) or 'length', optional\n",
        "              Type of output: max string list or max length\n",
        "\n",
        "  Returns:\n",
        "  --------\n",
        "    output = 'stringList': list\n",
        "                           List of characters of ONLY 1 longest subsequence (there maybe more)\n",
        "    output = 'length'    : int\n",
        "                           Length of longest subsequence \n",
        "\n",
        "  Examples:\n",
        "  ---------\n",
        "            T E  R   R   A   C   E     D     |    T E R R A C E D\n",
        "          C - -  -   -   -   C   C     C     |  C 0 0 0 0 0 1 1 1\n",
        "          R - -  R   R   R   R   R     R     |  R 0 0 1 1 1 1 1 1\n",
        "          A - -  R   R   RA  RA  RA    RA    |  A 0 0 1 1 2 2 2 2\n",
        "          T T T  R   R   RA  RA  RA    RA    |  T 1 1 1 1 2 2 2 2\n",
        "          E T TE TE  TE  RA  RA  RAE   [RAE] |  E 1 2 2 2 2 2 3 3\n",
        "          R T TE TER TER TER TER [TER] [TER] |  R 1 2 3 3 3 3 3 3*\n",
        "\n",
        "      Both 'RAE' and 'TER' are longest subsequences. This algorithm only returns\n",
        "      'TER' (right bottom of the table). To return more, please add 2 more neighbors\n",
        "      of right bottom if they also have the same length.\n",
        "\n",
        "    >>> strList1 = 'T E R R A C E D'.split()\n",
        "    >>> strList2 = 'C R A T E R'.split()\n",
        "    >>> LCS = LongestCommonSubsequence(strList1,strList2,output='stringList')\n",
        "    >>> print(LCS)\n",
        "    ['T', 'E', 'R']\n",
        "    >>> maxLength = LongestCommonSubsequence(strList1,strList2,output='length')\n",
        "    >>> print(maxLength)\n",
        "    3\n",
        "\n",
        "    >>> strList1 = list('SHINCHAN')\n",
        "    >>> strList2 = list('NOHARAAA')\n",
        "    >>> LCS = LongestCommonSubsequence(strList1,strList2,output='stringList')\n",
        "    >>> print(LCS)\n",
        "    ['N', 'H', 'A']\n",
        "\n",
        "    >>> strList1 = '16 27 60 76 123 88 55 94 57'.split()\n",
        "    >>> strList2 = '27 76 88 0 55 2 94 70 34 42 47'.split()\n",
        "    >>> LCS = LongestCommonSubsequence(strList1,strList2,output='stringList')\n",
        "    >>> print(LCS)\n",
        "    ['27', '76', '88', '55', '94']\n",
        "\n",
        "  References:\n",
        "    https://en.wikipedia.org/wiki/Longest_common_subsequence_problem\n",
        "    https://www.geeksforgeeks.org/python-program-for-longest-common-subsequence/\n",
        "'''\n",
        "\n",
        "def LongestCommonSubsequence(strList1, strList2, output='stringList'):\n",
        "  # Choose the longer length \n",
        "  L = max(len(strList1),len(strList2)) \n",
        "  # Dynamic programming memory for lengths\n",
        "  dp_L = [ [0]*(L+1) for _ in range(L+1)]\n",
        "  # Dynamic programming memory for strings\n",
        "  dp_S = [ [[]]*(L+1) for _ in range(L+1)]\n",
        "\n",
        "  for i in range(0,len(strList1)):\n",
        "    for j in range(0,len(strList2)):\n",
        "      if strList1[i] == strList2[j]:\n",
        "        dp_L[i+1][j+1] = dp_L[i][j] + 1\n",
        "        dp_S[i+1][j+1] = dp_S[i][j] + [strList1[i]]\n",
        "      else:\n",
        "        dp_L[i+1][j+1] = max(dp_L[i][j+1],dp_L[i+1][j])\n",
        "        if dp_L[i][j+1] >= dp_L[i+1][j]: dp_S[i+1][j+1] = dp_S[i][j+1]\n",
        "        else: dp_S[i+1][j+1] = dp_S[i+1][j]\n",
        "\n",
        "  # 2 ways of output: max string lists or max lengths\n",
        "  if output == 'stringList': \n",
        "    # ONLY 1 longest subsequence, modify codes to return more\n",
        "    return dp_S[len(strList1)][len(strList2)] \n",
        "  elif output == 'length': \n",
        "    return dp_L[len(strList1)][len(strList2)]"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}