# Dynamic Levenshtein

Previously, I had looked at calculating the Levenshtein distance between two strings. In that post I did some hand waving and claimed that the dynamic implementation will not register with the time command. Well I decided to test that claim and here is the proof.

``````#include <iostream>
#include <string>
using namespace std;
int minimum(int d, int i, int s);

int main(){
string s, t;
cin >> s >> t;
int sl = s.length()+1;
int tl = t.length()+1;
int* previous = new int[sl];
int* current = new int[sl];
//initialize current
for(int j=0; j<sl; ++j) *(current+j) = j;
for(int j=1; j<tl; ++j){
//Swap current and previous
int* tmp = previous;
previous = current;
current = tmp;
*(current) = j;
for(int k=1; k<sl; ++k){
if(s.at(k-1) == t.at(j-1)) *(current+k) = *(previous+k-1);
else{
*(current+k) = minimum(*(previous+k),*(current+k-1),*(previous+k-1))+1;
}
}
}
cout << *(current+sl-1) << endl;
return 0;
}

int minimum(int d, int i, int s){
int min = d;
if(i < min) min = i;
if(s < min) min = s;
return min;
}
``````