#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

map< vector< string >, int > lev_cache;

int levenshtein_distance(string l1, string l2) {
	if (l1 == l2) return 0;
	if (l1 == "" && l2 != "") return l2.length();
	if (l1 != "" && l2 == "") return l1.length();
	
	vector< string > temp; temp.push_back(l1); temp.push_back(l2); //vector< string > temp = {l1, l2};
	if (lev_cache.count(temp) > 0) return lev_cache[temp];
	
	string l1_1, l1_rest, l2_1, l2_rest;
	l1_1 = l1.substr(0,1);
	l1_rest = l1.substr(1);
	l2_1 = l2.substr(0,1);
	l2_rest = l2.substr(1);
	if (l2_1 == l1_1) {
			int d = levenshtein_distance(l1_rest, l2_rest);
			temp.clear(); temp.push_back(l1_rest); temp.push_back(l2_rest); //temp = {l1_rest, l2_rest};
			lev_cache[temp] = d;
			return d;
	}
	int m1 = levenshtein_distance(l1_rest, l2);
	temp.clear(); temp.push_back(l1_rest); temp.push_back(l2); //temp = {l1_rest, l2};
	lev_cache[temp] = m1;
	int m2 = levenshtein_distance(l1, l2_rest);
	temp.clear(); temp.push_back(l1); temp.push_back(l2_rest); //temp = {l1, l2_rest};
	lev_cache[temp] = m2;
	int m3 = levenshtein_distance(l1_rest, l2_rest);
	temp.clear(); temp.push_back(l1_rest); temp.push_back(l2_rest); //temp = {l1_rest, l2_rest};
	lev_cache[temp] = m3;
	return 1 + min(min(m1, m2), m3);
}

int main(int argc, char **argv)
{
	cout << "Distance: " << levenshtein_distance("the quick brown fox jumps over the lazy dog", "pack my box with five dozen liquor jugs") << "\n";
	//cout << "Distance: " << levenshtein_distance("the quick brown fox", "pack my box") << "\n";
}