{"id":3579,"date":"2023-10-30T19:53:01","date_gmt":"2023-10-30T14:23:01","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3579"},"modified":"2023-10-30T19:53:03","modified_gmt":"2023-10-30T14:23:03","slug":"edit-distance-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/edit-distance-problem\/","title":{"rendered":"Edit Distance Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">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=\"#approach-1-recursion\">Approach 1: Recursion<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-dynamic-programming\">Efficient Approach: Dynamic Programming<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-edit-distance-problem\">Q.1: What is the edit distance problem?<\/a><\/li><li><a href=\"#q2-what-is-the-time-and-space-complexity-of-the-dynamic-programming-approach\">Q.2: What is the time and space complexity of the dynamic programming approach?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given two strings <strong>A<\/strong> and <strong>B<\/strong>, find the minimum number of steps required to convert <strong>A<\/strong> to <strong>B<\/strong>. (each operation is counted as 1 step.)<\/p>\n\n\n\n<p>You have the following 3 operations permitted on a word:<\/p>\n\n\n\n<ul><li>Insert a character<\/li><li>Delete a character<\/li><li>Replace a character<\/li><\/ul>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>A = \u201cabad\u201d, B = \u201cabac\u201d<br><strong>Output: <\/strong>1<br><strong>Explanation: <\/strong>Operation 1: Replace <strong>d<\/strong> with <strong>c<\/strong>.<\/p>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;A = \u201chorse\u201d, B = \u201cro\u201d<br><strong>Output:<\/strong> 3<\/p>\n\n\n\n<h2 id=\"approach-1-recursion\">Approach 1: Recursion<\/h2>\n\n\n\n<p id=\"the-idea-is-to-use-a-recursive-approach-to-solve-the-problem-all-the-characters-of-both-the-strings-are-traversed-one-by-one-either-from-the-left-or-the-right-end-and-apply-the-given-operations\">The idea is to use a recursive approach to solve the problem.<br>All the characters of both the strings are traversed one by one either from the left or the right end and apply the given operations.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"746\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3743 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\/Image-4-1-1024x746.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-4-1-1024x746.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-4-1-300x219.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-4-1-768x560.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-4-1-380x277.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-4-1-550x401.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-4-1-800x583.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-4-1-1160x846.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-4-1.png 1354w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Consider two pointers <strong>i<\/strong> and <strong>j<\/strong> pointing the given string <strong>A<\/strong> and <strong>B<\/strong>.<\/li><li>If the current character, pointing in both the strings are same, then no changes are to be made. Therefore, recurse for lengths <strong>i + 1<\/strong> and <strong>j + 1<\/strong>.<\/li><li>Otherwise, try to apply the free operations provided.<ul><li>Each of the given operations would cause <strong>1<\/strong> units.<\/li><li>The character pointer <strong>i<\/strong> points to is A[i] and pointer <strong>j <\/strong>is B[j]. Therefore, F(i, j ) is the <strong>edit<\/strong> <strong>distance <\/strong>of <strong>A(0,i) <\/strong>and <strong>B(0, j)<\/strong>.<\/li><li>For insertion: Recurse <strong>i &#8211; 1 <\/strong>to <strong>j<\/strong>.<\/li><li>For deletion: Recurse <strong>i<\/strong> to <strong>j &#8211; 1<\/strong>.<\/li><li>For replacement: Recurse <strong>i &#8211; 1<\/strong> to <strong>j &#8211; 1<\/strong>.<\/li><\/ul><\/li><li>After applying all the operations, <strong>f(i, j) = 1&nbsp; + min(f(i &#8211; 1, j), f(i, j &#8211; 1), f(i &#8211; 1, j &#8211; 1))<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\"><span id=\"c-implementation-2\">C++ Implementation<\/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=\"\">int editDistanceHelper(int i, int j, string &amp; str1, string &amp; str2) {\n  if (i == 0) {\n    return j;\n  }\n \n  \n  if (j == 0) {\n    return i;\n  }\n  \n  int ans = 1 + min({\n    editDistanceHelper(i, j - 1, str1, str2), \/\/ Insert\n    editDistanceHelper(i - 1, j, str1, str2), \/\/ Remove\n    editDistanceHelper(i - 1, j - 1, str1, str2) \/\/ Replace\n  });\n \n  if (str1[i - 1] == str2[j - 1]) {\n    ans = min(ans, editDistanceHelper(i - 1, j - 1, str1, str2));\n  }\n  return ans;\n}\n \nint editDistance(string str1, string str2) {\n \n  int n = str1.size() + 1, m = str2.size() + 1;\n \n  int ans = editDistanceHelper(n, m, str1, str2);\n \n  return ans;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\"><span id=\"java-implementation-2\">Java Implementation<\/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=\"\">private static int editDistanceHelper(int i, int j, String str1, String str2) {\n  if (i == 0) {\n    return j;\n  }\n \n  if (j == 0) {\n    return i;\n  }\n \n  int ans = 1 + Math.min(Math.min(\n      editDistanceHelper(i, j - 1, str1, str2), \/\/ Insert\n      editDistanceHelper(i - 1, j, str1, str2)), \/\/ Remove\n    editDistanceHelper(i - 1, j - 1, str1, str2) \/\/ Replace\n  );\n \n  if (str1.charAt(i - 1) == str2.charAt(j - 1)) {\n    ans = Math.min(ans, editDistanceHelper(i - 1, j - 1, str1, str2));\n  }\n \n  return ans;\n}\n \npublic static int editDistance(String str1, String str2) {\n \n  int n = str1.length(), m = str2.length();\n  int ans = editDistanceHelper(n, m, str1, str2);\n \n  return ans;\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\"><span id=\"python-implementation-2\">Python Implementation<\/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 editDistanceHelper(i, j, str1, str2):\n \n    if i == 0:\n \n        return j\n \n    if j == 0:\n \n        return i\n \n    ans = 1 + min(\n        {\n            editDistanceHelper(i, j - 1, str1, str2),  # Insert\n            editDistanceHelper(i - 1, j, str1, str2),  # Remove\n            editDistanceHelper(i - 1, j - 1, str1, str2),  # Replace\n        }\n    )\n \n    if str1[i - 1] == str2[j - 1]:\n        ans = min(ans, editDistanceHelper(i - 1, j - 1, str1, str2))\n \n    return ans\n \n \ndef editDistance(str1, str2):\n \n    n = len(str1)\n    m = len(str2)\n    ans = editDistanceHelper(n, m, str1, str2)\n \n    return ans<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(3^(N * M)), where N and M is the length of the first and second string.<br><strong>Space Complexity:<\/strong>O(N + M), where N and M is the length of the first and second string.<\/p>\n\n\n\n<h2 id=\"efficient-approach-dynamic-programming\">Efficient Approach: Dynamic Programming<\/h2>\n\n\n\n<p>The idea is to use a <a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>dynamic programming<\/strong><\/a> approach here. The tabulation method is the most efficient method to solve this problem.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"402\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3744 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\/Image-2-7-1024x402.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-7-1024x402.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-7-300x118.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-7-768x301.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-7-380x149.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-7-550x216.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-7-800x314.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-7-1160x455.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-7.png 1269w\" ><\/figure>\n\n\n\n<p>As stated earlier, since the problem has overlapping subproblems, many of the calculations are repeated.&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"662\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3745 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\/Image-3-3-1024x662.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3-1024x662.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3-300x194.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3-768x496.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3-230x150.png 230w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3-380x246.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3-550x355.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3-800x517.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3-1160x750.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-3.png 1354w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialise a <strong>2D dp<\/strong>, where <strong>dp[i][j] <\/strong>denotes the <strong>edit distance <\/strong>of the length (<strong>i + 1)th<\/strong> of <strong>A<\/strong> and (<strong>j + 1)th<\/strong> length of <strong>B.<\/strong><\/li><li>The recurrence relation is as follows:<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"339\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3746 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\/Image-7-1024x339.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-7-1024x339.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-7-300x99.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-7-768x254.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-7-380x126.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-7-550x182.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-7-800x265.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-7-1160x384.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-7.png 1280w\" ><\/figure>\n\n\n\n<ul><li>If current character of both the strings are same:<strong>dp[i][j] = dp[i &#8211; 1][j &#8211; 1]<\/strong><\/li><li>If current character of both the strings are different:<strong>dp[i][j] = 1 + min(dp[i &#8211; 1][j &#8211; 1], dp[i &#8211; 1][j], dp[i][j &#8211; 1])<\/strong><\/li><\/ul>\n\n\n\n<p>&nbsp;Let us understand this by an example :<\/p>\n\n\n\n<p>This example dry runs all the possible <strong>edit distances<\/strong> of the two words <strong>HORSE <\/strong>and <strong>ROS<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"712\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3747 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\/Image-1-9-1024x712.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-9-1024x712.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-9-300x209.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-9-768x534.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-9-380x264.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-9-550x382.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-9-800x556.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-9-1160x806.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-9.png 1269w\" ><\/figure>\n\n\n\n<p>Similarly, the tabular computations are done as follows :<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"574\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3748 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\/Image-5-1-1024x574.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-5-1-1024x574.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-5-1-300x168.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-5-1-768x430.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-5-1-380x213.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-5-1-550x308.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-5-1-800x448.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-5-1-1160x650.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-5-1.png 1476w\" ><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"662\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3749 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\/Image-6-1024x662.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6-1024x662.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6-300x194.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6-768x496.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6-230x150.png 230w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6-380x246.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6-550x355.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6-800x517.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6-1160x749.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-6.png 1280w\" ><figcaption> <\/figcaption><\/figure>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/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=\"\">int editDistance(string str1, string str2)\n{\n    int n = str1.size(), m = str2.size();\n    int **dp = new int *[n + 1];\n \n    for (int i = 0; i &lt;= n; i++)\n    {\n        dp[i] = new int[m + 1];\n    }\n \n    for (int i = 0; i &lt;= n; i++)\n    {\n        for (int j = 0; j &lt;= m; j++)\n        {\n            if (i == 0)\n            {\n                dp[i][j] = j;\n            }\n \n            else if (j == 0)\n            {\n                dp[i][j] = i;\n            }\n            else if (str1[i - 1] == str2[j - 1])\n            {\n                dp[i][j] = dp[i - 1][j - 1];\n            }\n            else\n            {\n                dp[i][j] = 1 + min(min(dp[i][j - 1],\n                                       dp[i - 1][j]),\n                                   dp[i - 1][j - 1]);\n            }\n        }\n    }\n    int ans = dp[n][m];\n    for (int i = 0; i &lt;= n; i++)\n    {\n        delete[] dp[i];\n    }\n \n    delete[] dp;\n    return ans;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/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 int editDistance(String str1, String str2) \n    {\n \n        int n = str1.length(), m = str2.length();\n        int[][] dp = new int [n + 1][m + 1];\n \n    \n        for (int i = 0; i &lt;= n; i++) \n        {\n            for (int j = 0; j &lt;= m; j++) \n            {\n                \n \n                if (i == 0) \n                {\n                    dp[i][j] = j;\n                }\n \n                else if (j == 0) \n                {\n                    dp[i][j] = i;\n                }\n \n                else if (str1.charAt(i - 1) == str2.charAt(j - 1)) \n                {\n                    dp[i][j] = dp[i - 1][j - 1];\n                }\n \n                else \n                {\n                    dp[i][j] = 1 + Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]);\n                }\n            }\n        }\n\n        int ans = dp[n][m];\n \n        return ans;\n    }<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/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=\"\">INT_MAX = 10000000\n \n \ndef editDistance(str1, str2):\n \n    n = len(str1)\n    m = len(str2)\n \n    dp = [[INT_MAX for i in range(m + 1)] for j in range(n + 1)]\n \n    for i in range(n + 1):\n \n        for j in range(m + 1):\n \n            if i == 0:\n                dp[i][j] = j\n \n            elif j == 0:\n                dp[i][j] = i\n \n            elif str1[i - 1] == str2[j - 1]:\n                dp[i][j] = dp[i - 1][j - 1]\n \n            else:\n                dp[i][j] = 1 + min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1])\n \n    ans = dp[n][m]\n \n    return ans<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(N * M), where N and M is the length of the first and second string.<br><strong>Space Complexity: <\/strong>O(N * M), where N and M is the length of the first and second string.<\/p>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/edit-distance\/\" target=\"_blank\">Edit Distance<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-what-is-the-edit-distance-problem\"><span id=\"q-1-what-is-the-edit-distance-problem\">Q.1: What is the edit distance problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The edit distance problem is the minimum number of insertions, deletions, or replacements required to convert one string to another.<\/p>\n\n\n\n<h3 id=\"q2-what-is-the-time-and-space-complexity-of-the-dynamic-programming-approach\"><span id=\"q-2-what-is-the-time-and-space-complexity-of-the-dynamic-programming-approach\">Q.2: What is the time and space complexity of the dynamic programming approach?<\/span><\/h3>\n\n\n\n<p><strong>Ans<\/strong>: The time and space complexity of the dynamic programming approach is O(N * M)\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given two strings A and B, find the minimum number of steps required to convert A&hellip;\n","protected":false},"author":5,"featured_media":3757,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","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":[399,552],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3579"}],"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=3579"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3579\/revisions"}],"predecessor-version":[{"id":25938,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3579\/revisions\/25938"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3757"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3579"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3579"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3579"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}