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

Levenshtein distance measures string similarity by counting changes needed to convert one string to another using dynamic programming.

The Levenshtein distance algorithm

Explanation

Using sub-problems

Understanding the array

Code