Edit Distance Problem

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see edit distance problem in java. Sometimes this problem also referred as "String distance replacement in java"

Problem

Given two strings string1 and string2, String1 is to be converted into String2 with the given operations available in the minimum number of steps. Using any one of the given operations contributes to the increment of steps by one.

Allowed Operations are :
(i) `Remove` : This operation allows the Removal any one character from String.
(ii) `Insert` : This operation allows the Insertion of one character at any spot in the String.
(iii) `Replace` : This operation allows the replacement of any one character in the string with
any other character.

Input:
bacbbd
cabddb
Output: 4

Solution

Naive Approach :

We will process the strings from start, and move towards the end solving the problem for the current character.

• If the current character of the strings match, we don’t do any operation to make them equal and we recur for the remaining Strings.
• If the current character of the strings does not match, we make three calls for the three operations, add one to the total number of operations took to make the Strings equal and recur for remaining subproblem depending on the type of operation, i.e.
• For explaining let us define remaining String as the substring of the actual string which does not include the first character i.e remaining string = substring(1, string.length).
(i) for removal : we recur for remaining_String1 and String2.
(ii) for insertion : we recur for String1 and remaining_String2.
(iii) for replacement : we recur for remaining_String1 and remaining_String2.

As at every point we are making 3 calls when character is different, and one call when character matches, Considering the worst case, let’s assume that no character in either string matches, then at every character we need to make 3 calls.
let’s define ‘n’ as the minimum(string1.length(), string2.length()).
therefore, the worst time complexity of the algorithm would be O(3^n).

EFFICIENT APPROACH :
We can definitely see overlapping subproblems in the recursive solution where the result for the same problem is being calculated again and again which increases the complexity to such a higher extent. Also the result for the bigger problem is being calculated using the optimal result of its smaller subproblems which we can see in the code of our previous algorithm. As this algorithm follow both the required properties of Dynamic programming, that is, Optimal substructure and Overlapping Subproblems, hence, this problem points to the use of Dynamic programming to reduce the complexity of the algorithm, where the result for a duplicate call will not be calculated again and again.

Algorithm:

• We make a 2D DP array for storing our result for the subproblems.
• Lets name it DP and its size will be `(string1.length + 1)*(string2.length + 1)`
• Any cell(i, j) will contain the result for the the number of operations needed to make the two strings  `(String1.substring(i, string1.length()))&(String2.substring(j, string2.length()))` matching.
• The last Row of the matrix will contain the result of : ```(String1.substring(current column, string1.length) & empty string2 ```
• `The last column of the matrix will contain the result of : empty string1 & (String1.substring(current column, string1.length))`
• ``` ```
``` @media only screen and (min-width: 0px) and (min-height: 0px) { div[id^="bsa-zone_1645544976895-5_123456"] { min-width: 300px; min-height: 250px; } } @media only screen and (min-width: 800px) and (min-height: 0px) { div[id^="bsa-zone_1645544976895-5_123456"] { min-width: 300px; min-height: 250px; } } The last two points actually are the base cases of our problem and we move backward to calculate the result of the bigger subproblem, How? Suppose we are calculating the result of a cell, DP[row][col] Now if the character of String1 at current column matches the character of String2 at current row, DP[row][col] = DP[row + 1][col + 1] This is basically equivalent to the call for the result of (remaining_String1, remaining String2), as the current character matches, so we dont need to do any operations for making them equal. What if the character of String1 at current column does not matches the character of String2 at current row, then the result for the current cell will be, DP[row][col] = min of(DP[row + 1][col], DP[row][col+1], DP[row + 1][col + 1])which is equivalent to Minimum of call for all three operations, that is, @media only screen and (min-width: 0px) and (min-height: 0px) { div[id^="bsa-zone_1645545087580-5_123456"] { min-width: 300px; min-height: 250px; } } @media only screen and (min-width: 800px) and (min-height: 0px) { div[id^="bsa-zone_1645545087580-5_123456"] { min-width: 300px; min-height: 250px; } } (i)  for removal : DP[row][col + 1], that is, remaining_String1 and String2 (ii)  for insertion : DP[row + 1][col], that is, String1 and remaining_String2 (iii) for replacement : DP[row+1][col+1], that is, remaining_String1 and remaining_String2. Eventually the result i.e. the minimum number of operations required for making both the strings matching is at the cell, DP[0][0] which represents the result of both COMPLETE strings. EditDistance.java 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758  package org.arpit.java2blog; import java.util.Scanner; public class EditDistance {     public static void main(String[] args) {         Scanner scn = new Scanner(System.in);         String s1 = scn.nextLine();        String s2 = scn.nextLine();         System.out.println(editDist(s1, s2));     }     public static int editDist(String s1, String s2) {        int[][] dp = new int[s1.length() + 1][s2.length() + 1];         /* this is the last column of the matrix which          *  represents the result of empty string1         *  and string2 starting from current row.         */        for (int row = s2.length(); row >= 0; row--) {            dp[row][s1.length()] = s2.length() - row;        }         /* this is the last row of the matrix which        * represents the result of empty string2        *  and string1 starting from current col.        */        for (int col = s1.length(); col >= 0; col--) {            dp[s2.length()][col] = s1.length() - col;        }         for (int col = s1.length() - 1; col >= 0; col--) {            for (int row = s2.length() - 1; row >= 0; row--) {                 /* If characters are same, then the solution will be without                  * these characters */                if (s1.charAt(col) == s2.charAt(row)) {                    dp[row][col] = dp[row + 1][col + 1];                } else {                /* else it will be minimum of these three operations                */                dp[row][col] = 1 + Math.min(dp[row + 1][col + 1], // replace                                Math.min(dp[row][col + 1]  //   removal                                , dp[row + 1][col]));   // insertion                }            }        }         return dp[0][0];    }}  That's all about Edit Distance Problem in java or String distance replacement in java. Was this post helpful? Let us know if you liked the post. That’s the only way we can improve. ```
``` ```
``` Share this Prev Sliding Window Maximum in java Next Find the local minima in array ```
``` Related PostsBinary Tree PostOrder traversal in javaPrint maximum occurring character in a StringQueue implementation in javaLowest Common Ancestor (LCA) for n-ary TreeFind first repeating element in an array of integersLargest Rectangular Area in a HistogramImplement stack using Linked List in javaMemoization example in javaBinary Tree Level Order traversal in javaLongest common Subsequence ```
``` ```
``` ```
``` Author Ayush Kumar Follow Author Related Posts Algorithm 18 June Maximum Number of Vowels in a Substring of Given Length Table of ContentsApproach – 1 Generate All Substrings Using substring() MethodApproach – 2 Using Sliding Window Method (Linear Time Solution) In this article, we will look at an interesting problem related to the Strings and [Sliding-Window Algorithm](https://java2blog.com/sliding-window-maximum-java/ “Sliding-Window Algorithm”). The problem is : "Given a String we have to Find the Maximum Number of Vowel […] Read More AlgorithmArray 04 June Search for a range Leetcode – Find first and last position of element in sorted array Table of ContentsApproach 1 (Using Linear Search)Approach 2 (Using Modified Binary Search-Optimal) In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is […] Read More AlgorithmStack 30 April Convert Postfix to Infix in Java Learn about how to convert Postfix to Infix in java. Read More AlgorithmStack 30 April Convert Prefix to Postfix in Java Learn about how to convert Prefix to Postfix in java. Read More AlgorithmAlgorithm Interview 16 April Data Structures in java Table of ContentsArray Declare and initialize array in javaAdvantages of arrayDisadvantages of array ExampleArray practice programsStackStack implementation using ArrayStack implementation using LinkedListImplementationPractice ProgramsQueueQueue implementation using arrayQueue implementation using LinkedListImplementationLinkedListImplementationLinkedList Practice ProgramsBinary treeImplementationBinary tree practice programsBinary Search treeImplementationBinary search tree Practice programsTrieImplementationHeapImplementationGraphImplementation Inbuild data structures in javaStringHashMapLinkedHashMapArrayListLinkedListHashSet In this post, we will see about various data […] Read More AlgorithmAlgorithm InterviewCore Java interview 29 November Top 100+ Java coding interview questions Table of ContentsStringQuestion 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?Question 2 : Write a java program to check if two Strings are anagram in java?Question 3 : Write a program to check if String has all unique characters in java?Question 4 : […] Read More Leave a Reply Your email address will not be published. Required fields are marked *Comment * Name * Email * Website Save my name, email, and website in this browser for the next time I comment. Δdocument.getElementById( "ak_js_1" ).setAttribute( "value", ( new Date() ).getTime() ); ```
``` Subscribe to our newletter Get quality tutorials to your inbox. Subscribe now. CategoriesCore java Interview Algorithm Python Spring Frameworks Popular PostsCore Java Tutorial with Examples for Beginners & Experienced Spring Tutorial Spring Boot tutorial Java 8 Stream Garbage Collection in java Top 100+ Java coding interview questions Let’s be Friends Facebook Twitter LinkedIn © 2020 Java2Blog ```
``` function showhide_toggle(a,b,d,f){var e=jQuery("#"+a+"-link-"+b),c=jQuery("a",e),g=jQuery("#"+a+"-content-"+b);a=jQuery("#"+a+"-toggle-"+b);e.toggleClass("sh-show sh-hide");g.toggleClass("sh-show sh-hide").toggle();"true"===c.attr("aria-expanded")?c.attr("aria-expanded","false"):c.attr("aria-expanded","true");a.text()===d?a.text(f):a.text(d)}; /* <![CDATA[ */ var PT_CV_PUBLIC = {"_prefix":"pt-cv-","page_to_show":"5","_nonce":"45df735282","is_admin":"","is_mobile":"","ajaxurl":"https:\/\/java2blog.com\/wp-admin\/admin-ajax.php","lang":"","loading_image_src":"data:image\/gif;base64,R0lGODlhDwAPALMPAMrKygwMDJOTkz09PZWVla+vr3p6euTk5M7OzuXl5TMzMwAAAJmZmWZmZszMzP\/\/\/yH\/C05FVFNDQVBFMi4wAwEAAAAh+QQFCgAPACwAAAAADwAPAAAEQvDJaZaZOIcV8iQK8VRX4iTYoAwZ4iCYoAjZ4RxejhVNoT+mRGP4cyF4Pp0N98sBGIBMEMOotl6YZ3S61Bmbkm4mAgAh+QQFCgAPACwAAAAADQANAAAENPDJSRSZeA418itN8QiK8BiLITVsFiyBBIoYqnoewAD4xPw9iY4XLGYSjkQR4UAUD45DLwIAIfkEBQoADwAsAAAAAA8ACQAABC\/wyVlamTi3nSdgwFNdhEJgTJoNyoB9ISYoQmdjiZPcj7EYCAeCF1gEDo4Dz2eIAAAh+QQFCgAPACwCAAAADQANAAAEM\/DJBxiYeLKdX3IJZT1FU0iIg2RNKx3OkZVnZ98ToRD4MyiDnkAh6BkNC0MvsAj0kMpHBAAh+QQFCgAPACwGAAAACQAPAAAEMDC59KpFDll73HkAA2wVY5KgiK5b0RRoI6MuzG6EQqCDMlSGheEhUAgqgUUAFRySIgAh+QQFCgAPACwCAAIADQANAAAEM\/DJKZNLND\/kkKaHc3xk+QAMYDKsiaqmZCxGVjSFFCxB1vwy2oOgIDxuucxAMTAJFAJNBAAh+QQFCgAPACwAAAYADwAJAAAEMNAs86q1yaWwwv2Ig0jUZx3OYa4XoRAfwADXoAwfo1+CIjyFRuEho60aSNYlOPxEAAAh+QQFCgAPACwAAAIADQANAAAENPA9s4y8+IUVcqaWJ4qEQozSoAzoIyhCK2NFU2SJk0hNnyEOhKR2AzAAj4Pj4GE4W0bkJQIAOw==","is_mobile_tablet":"","sf_no_post_found":"No posts found.","lf__separator":","}; var PT_CV_PAGINATION = {"first":"\u00ab","prev":"\u2039","next":"\u203a","last":"\u00bb","goto_first":"Go to first page","goto_prev":"Go to previous page","goto_next":"Go to next page","goto_last":"Go to last page","current_page":"Current page is","goto_page":"Go to page"}; /* ]]> */ /* <![CDATA[ */ var eafl_public = {"home_url":"https:\/\/java2blog.com\/","ajax_url":"https:\/\/java2blog.com\/wp-admin\/admin-ajax.php","nonce":"71da75b2c6"}; /* ]]> */ /* <![CDATA[ */ var tocplus = {"smooth_scroll":"1","visibility_show":"show","visibility_hide":"hide","width":"100%","smooth_scroll_offset":"100"}; /* ]]> */ /* <![CDATA[ */ var helpful = {"ajax_url":"https:\/\/java2blog.com\/wp-admin\/admin-ajax.php","ajax_data":{"user_id":"1f7d7115461695c527727886cca90b56","_wpnonce":"e656584aef"},"translations":{"fieldIsRequired":"This field is required."},"user_voted":{"user_id":"1f7d7115461695c527727886cca90b56","post_id":6761,"action":"helpful_has_user_voted","_wpnonce":"7ff25b2b91"},"post_id":"6761","ajax_session":{"helpful_user":"1f7d7115461695c527727886cca90b56"}}; /* ]]> */ "use strict";var _createClass=function(){function defineProperties(target,props){for(var i=0;i<props.length;i++){var descriptor=props[i];descriptor.enumerable=descriptor.enumerable||!1,descriptor.configurable=!0,"value"in descriptor&&(descriptor.writable=!0),Object.defineProperty(target,descriptor.key,descriptor)}}return function(Constructor,protoProps,staticProps){return protoProps&&defineProperties(Constructor.prototype,protoProps),staticProps&&defineProperties(Constructor,staticProps),Constructor}}();function _classCallCheck(instance,Constructor){if(!(instance instanceof Constructor))throw new TypeError("Cannot call a class as a function")}var RocketBrowserCompatibilityChecker=function(){function RocketBrowserCompatibilityChecker(options){_classCallCheck(this,RocketBrowserCompatibilityChecker),this.passiveSupported=!1,this._checkPassiveOption(this),this.options=!!this.passiveSupported&&options}return _createClass(RocketBrowserCompatibilityChecker,[{key:"_checkPassiveOption",value:function(self){try{var options={get passive(){return!(self.passiveSupported=!0)}};window.addEventListener("test",null,options),window.removeEventListener("test",null,options)}catch(err){self.passiveSupported=!1}}},{key:"initRequestIdleCallback",value:function(){!1 in window&&(window.requestIdleCallback=function(cb){var start=Date.now();return setTimeout(function(){cb({didTimeout:!1,timeRemaining:function(){return Math.max(0,50-(Date.now()-start))}})},1)}),!1 in window&&(window.cancelIdleCallback=function(id){return clearTimeout(id)})}},{key:"isDataSaverModeOn",value:function(){return"connection"in navigator&&!0===navigator.connection.saveData}},{key:"supportsLinkPrefetch",value:function(){var elem=document.createElement("link");return elem.relList&&elem.relList.supports&&elem.relList.supports("prefetch")&&window.IntersectionObserver&&"isIntersecting"in IntersectionObserverEntry.prototype}},{key:"isSlowConnection",value:function(){return"connection"in navigator&&"effectiveType"in navigator.connection&&("2g"===navigator.connection.effectiveType||"slow-2g"===navigator.connection.effectiveType)}}]),RocketBrowserCompatibilityChecker}(); /* <![CDATA[ */ var RocketPreloadLinksConfig = {"excludeUris":"\/(?:.+\/)?feed(?:\/(?:.+\/?)?)?\$\/|\/(?:.+\/)?embed\/|\/(index\\.php\/)?wp\\-json(\/.*|\$)\/|\/refer\/|\/go\/|\/recommend\/|\/recommends\/","usesTrailingSlash":"1","imageExt":"jpg|jpeg|gif|png|tiff|bmp|webp|avif|pdf|doc|docx|xls|xlsx|php","fileExt":"jpg|jpeg|gif|png|tiff|bmp|webp|avif|pdf|doc|docx|xls|xlsx|php|html|htm","siteUrl":"https:\/\/java2blog.com","onHoverDelay":"100","rateThrottle":"3"}; /* ]]> */ (function() { "use strict";var r="function"==typeof Symbol&&"symbol"==typeof Symbol.iterator?function(e){return typeof e}:function(e){return e&&"function"==typeof Symbol&&e.constructor===Symbol&&e!==Symbol.prototype?"symbol":typeof e},e=function(){function i(e,t){for(var n=0;n<t.length;n++){var i=t[n];i.enumerable=i.enumerable||!1,i.configurable=!0,"value"in i&&(i.writable=!0),Object.defineProperty(e,i.key,i)}}return function(e,t,n){return t&&i(e.prototype,t),n&&i(e,n),e}}();function i(e,t){if(!(e instanceof t))throw new TypeError("Cannot call a class as a function")}var t=function(){function n(e,t){i(this,n),this.browser=e,this.config=t,this.options=this.browser.options,this.prefetched=new Set,this.eventTime=null,this.threshold=1111,this.numOnHover=0}return e(n,[{key:"init",value:function(){!this.browser.supportsLinkPrefetch()||this.browser.isDataSaverModeOn()||this.browser.isSlowConnection()||(this.regex={excludeUris:RegExp(this.config.excludeUris,"i"),images:RegExp(".("+this.config.imageExt+")\$","i"),fileExt:RegExp(".("+this.config.fileExt+")\$","i")},this._initListeners(this))}},{key:"_initListeners",value:function(e){-1<this.config.onHoverDelay&&document.addEventListener("mouseover",e.listener.bind(e),e.listenerOptions),document.addEventListener("mousedown",e.listener.bind(e),e.listenerOptions),document.addEventListener("touchstart",e.listener.bind(e),e.listenerOptions)}},{key:"listener",value:function(e){var t=e.target.closest("a"),n=this._prepareUrl(t);if(null!==n)switch(e.type){case"mousedown":case"touchstart":this._addPrefetchLink(n);break;case"mouseover":this._earlyPrefetch(t,n,"mouseout")}}},{key:"_earlyPrefetch",value:function(t,e,n){var i=this,r=setTimeout(function(){if(r=null,0===i.numOnHover)setTimeout(function(){return i.numOnHover=0},1e3);else if(i.numOnHover>i.config.rateThrottle)return;i.numOnHover++,i._addPrefetchLink(e)},this.config.onHoverDelay);t.addEventListener(n,function e(){t.removeEventListener(n,e,{passive:!0}),null!==r&&(clearTimeout(r),r=null)},{passive:!0})}},{key:"_addPrefetchLink",value:function(i){return this.prefetched.add(i.href),new Promise(function(e,t){var n=document.createElement("link");n.rel="prefetch",n.href=i.href,n.onload=e,n.onerror=t,document.head.appendChild(n)}).catch(function(){})}},{key:"_prepareUrl",value:function(e){if(null===e||"object"!==(void 0===e?"undefined":r(e))||!1 in e||-1===["http:","https:"].indexOf(e.protocol))return null;var t=e.href.substring(0,this.config.siteUrl.length),n=this._getPathname(e.href,t),i={original:e.href,protocol:e.protocol,origin:t,pathname:n,href:t+n};return this._isLinkOk(i)?i:null}},{key:"_getPathname",value:function(e,t){var n=t?e.substring(this.config.siteUrl.length):e;return n.startsWith("/")||(n="/"+n),this._shouldAddTrailingSlash(n)?n+"/":n}},{key:"_shouldAddTrailingSlash",value:function(e){return this.config.usesTrailingSlash&&!e.endsWith("/")&&!this.regex.fileExt.test(e)}},{key:"_isLinkOk",value:function(e){return null!==e&&"object"===(void 0===e?"undefined":r(e))&&(!this.prefetched.has(e.href)&&e.origin===this.config.siteUrl&&-1===e.href.indexOf("?")&&-1===e.href.indexOf("#")&&!this.regex.excludeUris.test(e.href)&&!this.regex.images.test(e.href))}}],[{key:"run",value:function(){"undefined"!=typeof RocketPreloadLinksConfig&&new n(new RocketBrowserCompatibilityChecker({capture:!0,passive:!0}),RocketPreloadLinksConfig).init()}}]),n}();t.run(); }()); /* <![CDATA[ */ var CrayonSyntaxSettings = {"version":"_2.7.2_beta","is_admin":"0","ajaxurl":"https:\/\/java2blog.com\/wp-admin\/admin-ajax.php","prefix":"crayon-","setting":"crayon-setting","selected":"crayon-setting-selected","changed":"crayon-setting-changed","special":"crayon-setting-special","orig_value":"data-orig-value","debug":""}; var CrayonSyntaxStrings = {"copy":"Press %s to Copy, %s to Paste","minimize":"Click To Expand Code"}; /* ]]> */ (function(\$) { \$(function() { \$(".post").find("a").each(function() { var link_href = \$(this).attr("href"); if (link_href.indexOf("#") == -1) { \$(this).attr("target", "_blank"); } }); }); })(jQuery); /* <![CDATA[ */ document.querySelectorAll("ul.nav-menu").forEach( ulist => { if (ulist.querySelectorAll("li").length == 0) { ulist.style.display = "none"; } } ); /* ]]> */ if( PT_CV_PAGINATION ) { PT_CV_PAGINATION.links = {"page_1":"https:\/\/java2blog.com\/edit-distance-problem\/","page_n":"https:\/\/java2blog.com\/edit-distance-problem\/?_page=_CVNUMBER_"}; } "use strict";function wprRemoveCPCSS(){var preload_stylesheets=document.querySelectorAll('link[data-rocket-async="style"][rel="preload"]');if(preload_stylesheets&&0<preload_stylesheets.length)for(var stylesheet_index=0;stylesheet_index<preload_stylesheets.length;stylesheet_index++){var media=preload_stylesheets[stylesheet_index].getAttribute("media")||"all";if(window.matchMedia(media).matches)return void setTimeout(wprRemoveCPCSS,200)}var elem=document.getElementById("rocket-critical-css");elem&&"remove"in elem&&elem.remove()}window.addEventListener?window.addEventListener("load",wprRemoveCPCSS):window.attachEvent&&window.attachEvent("onload",wprRemoveCPCSS); ```