<\/p>\n\n\n\n
The Edit Distance, also known as Levenshtein Distance, is a widely used algorithmic concept in computer science and natural language processing. It measures the similarity between two strings by calculating the minimum number of single-character insertions, deletions, or substitutions required to transform one string into the other.<\/p>\n\n\n\n
Step-by-Step Approach:<\/strong><\/p>\n\n\n\n Java Solution:<\/strong><\/p>\n\n\n\n Python Solution:<\/strong><\/p>\n\n\n\n Explanation of Java\/Python Solution:<\/strong><\/p>\n\n\n\n The Java and Python solutions implement the Edit Distance (Levenshtein Distance) problem using Dynamic Programming to find the minimum number of edit operations required to transform one string into another.<\/p>\n\n\n\n The The provided example with The Edit Distance, also known as Levenshtein Distance, is a widely used algorithmic concept in computer science and natural language processing. It measures the similarity between two strings by calculating the minimum number of single-character insertions, deletions, or substitutions required to transform one string into the other. Step-by-Step Approach: Java Solution: Python Solution: Explanation of […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"saved_in_kubio":false,"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"aioseo_notices":[],"kubio_ai_page_context":{"short_desc":"","purpose":"general"},"_links":{"self":[{"href":"https:\/\/techedges.in\/index.php\/wp-json\/wp\/v2\/pages\/103"}],"collection":[{"href":"https:\/\/techedges.in\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/techedges.in\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/techedges.in\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techedges.in\/index.php\/wp-json\/wp\/v2\/comments?post=103"}],"version-history":[{"count":3,"href":"https:\/\/techedges.in\/index.php\/wp-json\/wp\/v2\/pages\/103\/revisions"}],"predecessor-version":[{"id":117,"href":"https:\/\/techedges.in\/index.php\/wp-json\/wp\/v2\/pages\/103\/revisions\/117"}],"wp:attachment":[{"href":"https:\/\/techedges.in\/index.php\/wp-json\/wp\/v2\/media?parent=103"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
str1<\/code> and str2<\/code>.<\/li>\n\n\n\nstr1<\/code> into str2<\/code>.<\/li>\n\n\n\n(m+1) x (n+1)<\/code>, where m<\/code> and n<\/code> are the lengths of str1<\/code> and str2<\/code>, respectively.<\/li>\n\n\n\ndp[i][0] = i<\/code> and dp[0][j] = j<\/code>, representing the number of edit operations required to convert an empty string to str1<\/code> or str2<\/code>.<\/li>\n\n\n\n(1, 1)<\/code> to (m, n)<\/code>.<\/li>\n\n\n\n(i, j)<\/code> in the DP array, we check the characters at str1[i-1]<\/code> and str2[j-1]<\/code>. If they are equal, no edit operation is needed at this position, so we set dp[i][j]<\/code> to the same value as dp[i-1][j-1]<\/code>.<\/li>\n\n\n\n\n
dp[i][j] = dp[i][j-1] + 1<\/code><\/li>\n\n\n\ndp[i][j] = dp[i-1][j] + 1<\/code><\/li>\n\n\n\ndp[i][j] = dp[i-1][j-1] + 1<\/code><\/li>\n<\/ul>\n\n\n\n\n
dp[i][j]<\/code> to the minimum value among the three edit operations.<\/li>\n\n\n\ndp[m][n]<\/code> represents the minimum edit distance between str1<\/code> and str2<\/code>.<\/li>\n<\/ol>\n\n\n\npublic class EditDistance {\n\n public int minDistance(String word1, String word2) {\n int m = word1.length();\n int n = word2.length();\n\n int[][] dp = new int[m + 1][n + 1];\n\n for (int i = 0; i <= m; i++) {\n dp[i][0] = i;\n }\n\n for (int j = 0; j <= n; j++) {\n dp[0][j] = j;\n }\n\n for (int i = 1; i <= m; i++) {\n for (int j = 1; j <= n; j++) {\n if (word1.charAt(i - 1) == word2.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1];\n } else {\n int insertion = dp[i][j - 1] + 1;\n int deletion = dp[i - 1][j] + 1;\n int substitution = dp[i - 1][j - 1] + 1;\n dp[i][j] = Math.min(Math.min(insertion, deletion), substitution);\n }\n }\n }\n\n return dp[m][n];\n }\n\n public static void main(String[] args) {\n String word1 = \"intention\";\n String word2 = \"execution\";\n\n EditDistance editDistance = new EditDistance();\n System.out.println(\"Minimum Edit Distance: \" + editDistance.minDistance(word1, word2));\n }\n}<\/code><\/pre>\n\n\n\nclass EditDistance:\n\n def minDistance(self, word1: str, word2: str) -> int:\n m, n = len(word1), len(word2)\n\n dp = [[0] * (n + 1) for _ in range(m + 1)]\n\n for i in range(m + 1):\n dp[i][0] = i\n\n for j in range(n + 1):\n dp[0][j] = j\n\n for i in range(1, m + 1):\n for j in range(1, n + 1):\n if word1[i - 1] == word2[j - 1]:\n dp[i][j] = dp[i - 1][j - 1]\n else:\n insertion = dp[i][j - 1] + 1\n deletion = dp[i - 1][j] + 1\n substitution = dp[i - 1][j - 1] + 1\n dp[i][j] = min(insertion, deletion, substitution)\n\n return dp[m][n]\n\nif __name__ == \"__main__\":\n word1 = \"intention\"\n word2 = \"execution\"\n\n edit_distance = EditDistance()\n print(\"Minimum Edit Distance:\", edit_distance.minDistance(word1, word2))<\/code><\/pre>\n\n\n\nminDistance<\/code> method in Java and minDistance<\/code> method in Python take two input strings word1<\/code> and word2<\/code> and return the minimum edit distance between the two strings.<\/p>\n\n\n\nword1 = \"intention\"<\/code> and word2 = \"execution\"<\/code> demonstrates how the Dynamic Programming approach calculates the minimum edit distance as 5<\/code>. The minimum number of edit operations required to convert “intention” to “execution” is 5<\/code>, which includes 3 deletions and 2 insertions.<\/p>\n","protected":false},"excerpt":{"rendered":"