Approaches To Problem Solving #12(String | DP)
In our previous blog, we already started with the introduction to one of the problems that we are going to discuss. We will try to discuss further about the topics involved.
Let us revisit the problem statement,
Problem #1: Given two strings A and B, find the minimum edit distance between the two strings. Edit distance is defined using: (a) Deleting a character, (b) Inserting a character, (c) Replacing a character.
Let us consider the following example to get a clearer idea of this problem,
Since we are asked to find out the minimum number of moves to transform a source string into a target string, the problem hints us towards thinking in terms of Dynamic Programming.
Let us move forth and discuss how we can frame the states, base cases and transitions for the given problem to be solved using dynamic programming.
We need States, base cases and transitions to understand how our dynamic programming should work.
Approach #1: First of all, if we try to think about states, it seems pretty intuitive to keep two parameters with ourselves to determine a given state in our recursive solution. First one to tell us where we are currently on the first string and second to tell us where we are currently on the second string. We will try to add more parameters to define our state if necessary, as we progress.
With our states known, let us work on determining the transitions. We have three types of operations i.e., deleting, inserting and replacing a character from the source string.
a) Deleting a character :- Let us assume that we are on the ith position in source string ‘A’ and on the jth position in target string ‘B’. So when we plan to delete a character from string ‘A’, it is equivalent to increasing i by 1 and letting j stay as it is.
b) Inserting a character :- When we insert a character in source string ‘A’ at the current position, it is fair to assume that we only insert a character that is equal to jth character in string ‘B’. Since we are inserting a new character just before the ith character (for the sake of simplicity), for the next state, i stays as it is and j is increased by 1.
c) Replacing a character :- When we replace a character in source string ‘A’ at the current position, it is again beneficial to replace the ith character with a character that is equal to the jth character in string ‘B’. Hence, our new state should have i and j both incremented by 1.
Not to forget, we can choose not to perform any of these operations and it is intuitive to only skip these operations when the ith character in string ‘A’ and jth character in string ‘B’ match.
Formally,
if(A[i] == B[j]) : dp[i][j] = rec(i + 1, j + 1),
else : dp[i][j] = 1 + min(rec(i + 1, j), rec(i + 1, j + 1), rec(i, j + 1))
With our states and transitions defined, only part left is to define the base cases. If i and j are both beyond the lengths of the strings A and B respectively, we return 0. In all the other cases, in which one of either i or j has reached beyond the length of their respective strings, we add the remaining length of the other string to our answer, as the only option left to equate both the strings is to delete the remaining characters left over in the other string.
Thus, we have our solution!! Assuming that the source string ‘A’ has length N and the target string ‘B’ has length M, the time complexity for this solution is ~O(N * M).
In our next article, one of the problems that we are going to discuss is given below,
Problem : Given a two-dimensional matrix of integers containing 1s and 0s, return the total number of square submatrices with all 1s.
We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Strings and Dynamic Programming further!
We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.
For hugs and bugs, please comment down below. Till then.. Happy Coding!
More such posts can be found at :-
