{"id":25858,"date":"2017-10-25T21:53:31","date_gmt":"2017-10-25T16:23:31","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25858"},"modified":"2017-10-25T21:53:31","modified_gmt":"2017-10-25T16:23:31","slug":"java-programming-edit-distance","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-edit-distance\/","title":{"rendered":"Java Programming &#8211; Edit Distance"},"content":{"rendered":"<p>Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert \u2018str1\u2019 into \u2018str2\u2019.<\/p>\n<ul>\n<li>Insert<\/li>\n<li>Remove<\/li>\n<li>Replace<\/li>\n<\/ul>\n<p>All of the above operations are of equal cost.<br \/>\n<strong><br \/>\nExamples:<\/strong><\/p>\n<pre>Input:   str1 = \"geek\", str2 = \"gesek\"\r\nOutput:  1\r\nWe can convert str1 into str2 by inserting a 's'.\r\n\r\nInput:   str1 = \"cat\", str2 = \"cut\"\r\nOutput:  1\r\nWe can convert str1 into str2 by replacing 'a' with 'u'.\r\n\r\nInput:   str1 = \"sunday\", str2 = \"saturday\"\r\nOutput:  3\r\nLast three and first characters are same.  We basically\r\nneed to convert \"un\" to \"atur\".  This can be done using\r\nbelow three operations. \r\nReplace 'n' with 'r', insert t, insert a<\/pre>\n[ad type=&#8221;banner&#8221;]\n<p><strong>What are the subproblems in this case?<\/strong><br \/>\nThe idea is process all characters one by one staring from either from left or right sides of both strings.<br \/>\nLet we traverse from right corner, there are two possibilities for every pair of character being traversed.<\/p>\n<pre><strong>m:<\/strong> Length of str1 (first string)\r\n<strong>n:<\/strong> Length of str2 (second string)\r\n<\/pre>\n<ul>\n<li>If last characters of two strings are same, nothing much to do. Ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1.<\/li>\n<li>Else (If last characters are not same), we consider all operations on \u2018str1\u2019, consider all three operations on last character of first string, recursively compute minimum cost for all three operations and take minimum of three values.\n<ul>\n<li>Insert: Recur for m and n-1<\/li>\n<li>Remove: Recur for m-1 and n<\/li>\n<li>Replace: Recur for m-1 and n-1<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>Below is java\u00a0implementation of above Naive recursive solution.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ A Naive recursive Java program to find minimum number<br\/>\/\/ operations to convert str1 to str2<br\/>class EDIST<br\/>{<br\/>    static int min(int x,int y,int z)<br\/>    {<br\/>        if (x&lt;y &amp;&amp; x&lt;z) return x;<br\/>        if (y&lt;x &amp;&amp; y&lt;z) return y;<br\/>        else return z;<br\/>    }<br\/> <br\/>    static int editDist(String str1 , String str2 , int m ,int n)<br\/>    {<br\/>        \/\/ If first string is empty, the only option is to<br\/>    \/\/ insert all characters of second string into first<br\/>    if (m == 0) return n;<br\/>      <br\/>    \/\/ If second string is empty, the only option is to<br\/>    \/\/ remove all characters of first string<br\/>    if (n == 0) return m;<br\/>      <br\/>    \/\/ If last characters of two strings are same, nothing<br\/>    \/\/ much to do. Ignore last characters and get count for<br\/>    \/\/ remaining strings.<br\/>    if (str1.charAt(m-1) == str2.charAt(n-1))<br\/>        return editDist(str1, str2, m-1, n-1);<br\/>      <br\/>    \/\/ If last characters are not same, consider all three<br\/>    \/\/ operations on last character of first string, recursively<br\/>    \/\/ compute minimum cost for all three operations and take<br\/>    \/\/ minimum of three values.<br\/>    return 1 + min ( editDist(str1,  str2, m, n-1),    \/\/ Insert<br\/>                     editDist(str1,  str2, m-1, n),   \/\/ Remove<br\/>                     editDist(str1,  str2, m-1, n-1) \/\/ Replace                     <br\/>                   );<br\/>    }<br\/> <br\/>    public static void main(String args[])<br\/>    {<br\/>        String str1 = &quot;sunday&quot;;<br\/>        String str2 = &quot;saturday&quot;;<br\/>  <br\/>        System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) );<br\/>    }<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>3<\/pre>\n<p>The time complexity of above solution is exponential. In worst case, we may end up doing O(3<sup>m<\/sup>) operations. The worst case happens when none of characters of two strings match. Below is a recursive call diagram for worst case.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-25814\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Edit-Distance.png\" alt=\"Edit Distance\" width=\"1024\" height=\"618\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Edit-Distance.png 1024w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Edit-Distance-300x181.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Edit-Distance-768x464.png 768w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Edit-Distance-990x597.png 990w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/p>\n<p>We can see that many subproblems are solved again and again, for example eD(2,2) is called three times. Since same suproblems are called again, this problem has Overlapping Subprolems property. So Edit Distance problem has both properties (see <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/12635\" target=\"_blank\" rel=\"noopener\">this <\/a>and <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/12819\" target=\"_blank\" rel=\"noopener\">this<\/a>) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array that stores results of subpriblems.<\/p>\n[ad type=&#8221;banner&#8221;]\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ A Dynamic Programming based Java program to find minimum<br\/>\/\/ number operations to convert str1 to str2<br\/>class EDIST<br\/>{<br\/>    static int min(int x,int y,int z)<br\/>    {<br\/>        if (x &lt; y &amp;&amp; x &lt;z) return x;<br\/>        if (y &lt; x &amp;&amp; y &lt; z) return y;<br\/>        else return z;<br\/>    }<br\/> <br\/>    static int editDistDP(String str1, String str2, int m, int n)<br\/>    {<br\/>        \/\/ Create a table to store results of subproblems<br\/>        int dp[][] = new int[m+1][n+1];<br\/>      <br\/>        \/\/ Fill d[][] in bottom up manner<br\/>        for (int i=0; i&lt;=m; i++)<br\/>        {<br\/>            for (int j=0; j&lt;=n; j++)<br\/>            {<br\/>                \/\/ If first string is empty, only option is to<br\/>                \/\/ isnert all characters of second string<br\/>                if (i==0)<br\/>                    dp[i][j] = j;  \/\/ Min. operations = j<br\/>      <br\/>                \/\/ If second string is empty, only option is to<br\/>                \/\/ remove all characters of second string<br\/>                else if (j==0)<br\/>                    dp[i][j] = i; \/\/ Min. operations = i<br\/>      <br\/>                \/\/ If last characters are same, ignore last char<br\/>                \/\/ and recur for remaining string<br\/>                else if (str1.charAt(i-1) == str2.charAt(j-1))<br\/>                    dp[i][j] = dp[i-1][j-1];<br\/>      <br\/>                \/\/ If last character are different, consider all<br\/>                \/\/ possibilities and find minimum<br\/>                else<br\/>                    dp[i][j] = 1 + min(dp[i][j-1],  \/\/ Insert<br\/>                                       dp[i-1][j],  \/\/ Remove<br\/>                                       dp[i-1][j-1]); \/\/ Replace<br\/>            }<br\/>        }<br\/>  <br\/>        return dp[m][n];<br\/>    }<br\/> <br\/>     <br\/> <br\/>    public static void main(String args[])<br\/>    {<br\/>        String str1 = &quot;sunday&quot;;<br\/>        String str2 = &quot;saturday&quot;;<br\/>        System.out.println( editDistDP( str1 , str2 , str1.length(), str2.length()) );<br\/>    }<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>3<\/pre>\n<p>Time Complexity: O(m x n)<br \/>\nAuxiliary Space: O(m x n)<\/p>\n<p><strong>Applications<\/strong>: There are many practical applications of edit distance algorithm, refer <a href=\"http:\/\/en.wikipedia.org\/wiki\/Lucene\" target=\"_blank\" rel=\"noopener noreferrer\">Lucene<\/a> API for sample. Another example, display all the words in a dictionary that are near proximity to a given word\\incorrectly spelled word.<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Java Programming Edit Distance &#8211; Dynamic Programming &#8211; Idea is process all characters one by one staring from either from left or right sides of both string<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,70145,2139],"tags":[72847,72842,72845,70483,75727,72848,72840,72846,72987,72985,72843,72854,72844,75733,75731,75732,75734,76174,75736,75735,72850,72839,75729,75728,76173,72852,72855,72853,72851],"class_list":["post-25858","post","type-post","status-publish","format-standard","hentry","category-coding","category-dynamic-programming","category-java","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-and-edit-distance","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-java","tag-dynamic-programming-java","tag-dynamic-programming-problems","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-edit-distance-between-two-strings-example","tag-edit-distance-c","tag-edit-distance-calculator","tag-edit-distance-in-c","tag-edit-distance-in-java","tag-edit-distance-java","tag-edit-distance-recursive","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-minimum-edit-distance","tag-minimum-edit-distance-dynamic-programming","tag-minimum-edit-distance-in-java","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25858","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25858"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25858\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25858"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25858"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25858"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}