The **Levenshtein distance (a.k.a edit distance)** is a measure of similarity between two strings. It is defined as the minimum number of changes required to convert string `a` into string `b` (this is done by inserting, deleting or replacing a character in string `a`). The smaller the Levenshtein distance, the more similar the strings are. This is a very common problem in the application of [Dynamic Programming](https://www.educative.io/answers/what-is-dynamic-programming).

# Explanation
 ### Using sub-problems



A pre-requisite for applying Dynamic Programming, to solve a problem, is to demonstrate that the solution to the original problem can be found by using the solutions to the sub-problems.

The approach here is somewhat simple and intuitive. Consider the strings `a` and `b` up to their last character:
1. If the last characters of both strings are the same, then the edit distance is equal to the edit distance of the same two strings, up to their second-to-last character.
2. If the last character is different, then the edit distance is equal to the *minimum* of the cost of inserting, deleting, or replacing the last character of string `a`.

## Understanding the array

Since DP utilises memory for storing the solutions to sub-problems, we will use a 2D array (`D`) for this purpose.

The value in `D[i][j]` represents the edit distance *if* we consider the strings `a` and `b`, till their `i`th and `j`th character, respectively. Therefore, the answer to the original problem will be found in `D[length of 'a'][length of 'b']`.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int findMin(int x, int y, int z){
  if(x <= y && x <= z)
    return x;
  else if(y <=x && y <= z)
    return y;
  else
    return z;
}

void freeMemory(int** arr, int a, int b){
  for(int i = 0; i < a; i++){
    delete[] arr[i];
  }
  
  delete[] arr;
}

int findDistance(char a[], char b[]){
  // Declaring a 2D array on the heap dynamically:
  int len_a = strlen(a);
  int len_b = strlen(b);
  int** d = new int*[len_a + 1];
  for(int i = 0; i < len_a + 1; i++)
    d[i] = new int[len_b + 1];

  // Initialising first column:
  for(int i = 0; i < len_a + 1; i++)
    d[i][0] = i;

  // Initialising first row:
  for(int j = 0; j < len_b + 1; j++)
    d[0][j] = j;

  // Applying the algorithm:
  int insertion, deletion, replacement;

  for(int i = 1; i < len_a + 1; i++){
    for(int j = 1; j < len_b + 1; j++){
      if(a[i - 1] == b[j - 1]){
        d[i][j] = d[i - 1][j - 1];
      }
      else{
        // Choosing the best option:
        insertion = d[i][j - 1];
        deletion = d[i - 1][j];
        replacement = d[i - 1][j - 1];

        d[i][j] = 1 + findMin(insertion, deletion, replacement);
      }
    }
  }

  int answer = d[len_a][len_b];
  
  freeMemory(d, len_a + 1, len_b + 1);

  return answer;
}

int main() {
  char a[] = "Carry";
  char b[] = "Bark";

  cout << "Levenshtein Distance: " <<  findDistance(a, b);
  return 0;
}

public class main {

	public static void main(String[] args) {
		String a = "vanish", b = "tarnish";
    
		main lev = new main();
		System.out.println("Levenshtein Distance: " + lev.findDistance(a, b));
	}
	
	int findDistance(String a, String b) {
		int d[][] = new int[a.length() + 1][b.length() + 1];
		
		// Initialising first column:
		for(int i = 0; i <= a.length(); i++)
			d[i][0] = i;
		
		// Initialising first row:
		for(int j = 0; j <= b.length(); j++)
			d[0][j] = j;
		
		// Applying the algorithm:
		int insertion, deletion, replacement;
		for(int i = 1; i <= a.length(); i++) {
			for(int j = 1; j <= b.length(); j++) {
				if(a.charAt(i - 1) == (b.charAt(j - 1)))
					d[i][j] = d[i - 1][j - 1];
				else {
					insertion = d[i][j - 1];
					deletion = d[i - 1][j];
					replacement = d[i - 1][j - 1];
					
					// Using the sub-problems
					d[i][j] = 1 + findMin(insertion, deletion, replacement);
				}
			}
		}
		
		return d[a.length()][b.length()];
	}
	
  // Helper funciton used by findDistance()
	int findMin(int x, int y, int z) {
		if(x <= y && x <= z)
			return x;
		if(y <= x && y <= z)
			return y;
		else
			return z;
	}
}









Java

# Declaring the strings 'a' and 'b':
a = "junk"
b = "clunky"

# Declaring array 'D' with rows = len(a) + 1 and columns = len(b) + 1:
D = [[0 for i in range(len(b) + 1)] for j in range(len(a) + 1)]

# Initialising first row:
for i in range(len(a) + 1):
    D[i][0] = i

# Initialising first column:
for j in range(len(b) + 1):
    D[0][j] = j

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            D[i][j] = D[i - 1][j - 1]
        else:
            # Adding 1 to account for the cost of operation
            insertion = 1 + D[i][j - 1]
            deletion = 1 + D[i - 1][j]
            replacement = 1 + D[i - 1][j - 1]

            # Choosing the best option:
            D[i][j] = min(insertion, deletion, replacement)

print("Levenshtein Distance: ", D[len(a)][len(b)])









Python

The Levenshtein distance algorithm

The Levenshtein distance (a.k.a edit distance) is a measure of similarity between two strings. It is defined as the minimum number of changes required to convert string a into string b (this is done by inserting, deleting or replacing a character in string a). The smaller the Levenshtein distance, the more similar the strings are. This is a very common problem in the application of Dynamic Programming. Explanation Using sub-problems A pre-requisite for applying Dynamic Programming, to solve a problem, is to demonstrate that the solution to the original problem can be found by using the solutions to the sub-problems. The approach here is somewhat simple and intuitive. Consider the strings a and b up to their last character:  If the last characters of both strings are the same, then the edit distance is equal to the edit distance of the same two strings, up to their second-to-last character. If the last character is different, then the edit distance is equal to the minimum of the cost of inserting, deleting, or replacing the last character of string a.  Understanding the array Since DP utilises memory for storing the solutions to sub-problems, we will use a 2D array (D) for this purpose. The value in D[i][j] represents the edit distance if we consider the strings a and b, till their ith and jth character, respectively. Therefore, the answer to the original problem will be found in D[length of  a ][length of  b ]. 

The Levenshtein distance algorithm

Explanation

Using sub-problems

Understanding the array

Code