Levenshtein distance

levenshteinDistance.cpp

#include <iostream>

using namespace std;

int getMinValueInArray(int *inputArray, int arrayLength) {
    int minIndex = 0;
    for(int i = 1; i < arrayLength; i++) {
        if (inputArray[i] < inputArray[minIndex]) {
            minIndex = i;
        }
    }
    
    return inputArray[minIndex];
}

int computeLevenshteinDistance(string inputA, string inputB) {
    int numberOfRows = inputA.length() + 1;
    int numberOfColumns = inputB.length() + 1;
    
    int comparisonMatrix[numberOfRows][numberOfColumns] {};
    for (int i = 0; i < numberOfRows; i++) {
        comparisonMatrix[i][0] = i;
    }
    for (int i = 0; i < numberOfColumns; i++) {
        comparisonMatrix[0][i] = i;
    }
    
    int valArray[3];
    for (int i = 1; i < numberOfRows; i++) {
        for (int j = 1; j < numberOfColumns; j++) {
            int cost = (inputA[i-1] == inputB[j-1]) ? 0 : 1;
            valArray[0] = comparisonMatrix[i-1][j] + 1;
            valArray[1] = comparisonMatrix[i][j-1] + 1;
            valArray[2] = comparisonMatrix[i-1][j-1] + cost;
          
            comparisonMatrix[i][j] = getMinValueInArray(valArray, 3);;
        }
    }
    
    return comparisonMatrix[numberOfRows - 1][numberOfColumns - 1];
}

int main()
{
    string inputA = "myS";
    string inputB = "myStringd";
    printf("The Levenshtein distance between %s and %s is %d", inputA.c_str(), inputB.c_str(), computeLevenshteinDistance(inputA, inputB));
    
    return 0;
}