EditDistancePython.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e1c84b43-9a77-408a-833e-064ed019ec5a",
   "metadata": {},
   "source": [
    "Given: Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.  \n",
    "Allowed Operations:\n",
    "Insert\n",
    "Remove\n",
    "Replace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "aa8fb5b1-a3b6-44c4-ad29-364d4cb383a9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Edit Distance:  5\n"
     ]
    }
   ],
   "source": [
    "# input data-types: \n",
    "# s: string\n",
    "# t: string\n",
    "# output data-type: int\n",
    "\n",
    "#this is a slight different implemention as comparet to lecture, but the logic is same.\n",
    "def editDistance(s, t):\n",
    "    len_s = len(s)              #length of string s\n",
    "    len_t = len(t)              #length of string t\n",
    "    \n",
    "    DP = [[0 for i in range(len_t+1)] for j in range(len_s+1)]  #creating DP matrix dimensions: [len(s)+1][len(t)+1] \n",
    "    \n",
    "    for i in range(len_s+1):               #this for loop initialize first row and first column of DP matrix.   \n",
    "        for j in range(len_t+1):\n",
    "            if i == 0:                    #if row_number = 0 then initialize cell with column_number.\n",
    "                DP[i][j] = j\n",
    "            elif j == 0:\n",
    "                DP[i][j] = i               #if column_number = 0 then initialize cell with row_number.\n",
    "                \n",
    "    for i in range(1,len_s+1):              #this for loop will fill matrix according to optimal substructure\n",
    "        for j in range(1,len_t+1):\n",
    "            if s[i-1:i] == t[j-1:j]:          #if the characters are equal, then we dont need to substitue,insert and delete.\n",
    "                DP[i][j] = DP[i-1][j-1]         #Simply Copy operation will do.\n",
    "            else:                                                      #if the characters are unequal\n",
    "                DP[i][j] = 1 + min(DP[i][j-1],DP[i-1][j],DP[i-1][j-1]) #then selece minimum cost operation from insert, delete and substitute. \n",
    "    return DP[len_s][len_t]\n",
    "\n",
    "#Sample Testcase\n",
    "string1 = \"intention\"\n",
    "string2 = \"execution\"\n",
    "print(\"Edit Distance: \",editDistance(string1,string2))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}