Edit Distance DP Problem

Shaila Nasrin
Learn Coding Concepts with Shaila
5 min readJul 14, 2019

--

Edit distance problems is: if we are given two string word1 and word2 what is the minimum number of operation needed to transform a into b. The operations are: substitution, insertion and deletion. You can find this problem in interviewbit and leetcode.

In order to solve this problem, we have to be familiar with sub-string operation. Substations are contiguous sequence of characters within a string( from Wikipedia).Let’s say we have a string “horse” which goes from index 0 to 4. So, the sub-strings are: index ( 0, 0) -> ‘h’, (0,1) -> ‘ho’, (0 , 2)-> hor, (0, 3)-> ‘hors’, (0, 4) ->…

--

--