Levenshtein Distance

[Sneha421]

The Levenshtein distance is a string metric for measuring the difference between two sequences.

Input: Two Strings (Let's say A and B)
Output: Levenshtein Distance

In this problem, we need to find the minimum number of single-character edits (this could be insertions, substitutions, or deletions) that can convert one string to another (eg: A to B)

[Sneha421]

This problem follows a simple Dynamic Programming approach. I've worked on a Bioinformatics application of the same, for the comparison of two DNA Sequences in Python. I am very interested in coding out this algorithm in Java, and would like to take up this issue!

[ritweekraj2802]

Respected sir , please assign me this issue.
Below is explanation of problem
Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.

Insert
Remove
Replace
All of the above operations are of equal cost.

Examples:

Input: str1 = "peek", str2 = "pesek"
Output: 1
We can convert str1 into str2 by inserting a 's'.

Input: str1 = "cat", str2 = "cut"
Output: 1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input: str1 = "sunday", str2 = "saturday"
Output: 3
Last three and first characters are same. We basically
need to convert "un" to "atur". This can be done using
below three operations.
Replace 'n' with 'r', insert t, insert a

What are the subproblems in this case?
The idea is process all characters one by one staring from either from left or right sides of both strings.
Let us traverse from right corner, there are two possibilities for every pair of character being traversed.

m: Length of str1 (first string)
n: Length of str2 (second string)
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.
Else (If last characters are not same), we consider all operations on ‘str1’, consider all three operations on last character of first string, recursively compute minimum cost for all three operations and take minimum of three values.
Insert: Recur for m and n-1
Remove: Recur for m-1 and n
Replace: Recur for m-1 and n-1

[Sneha421]

Good morning!
This issue has still not been resolved. May I start working on it?

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions]

Please reopen this issue once you add more information and updates here. If this is not the case and you need some help, feel free to seek help from our Gitter or ping one of the reviewers. Thank you for your contributions!