LevenshteinDistance.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Containers/Array.h"
#include "CoreTypes.h"
#include "Templates/Invoke.h"
 
namespace Algo
{
    template <typename RangeAType, typename RangeBType>
    [[nodiscard]] int32 LevenshteinDistance(const RangeAType& RangeA, const RangeBType& RangeB)
    {
        const int32 LenA = GetNum(RangeA);
        const int32 LenB = GetNum(RangeB);
        //Early return for empty string
        if (LenA == 0)
        {
            return LenB;
        }
        else if (LenB == 0)
        {
            return LenA;
        }
 
        auto DataA = GetData(RangeA);
        auto DataB = GetData(RangeB);
 
        TArray<int32> OperationCount;
        //Initialize data
        OperationCount.AddUninitialized(LenB + 1);
        for (int32 IndexB = 0; IndexB <= LenB; ++IndexB)
        {
            OperationCount[IndexB] = IndexB;
        }
        //find the operation count
        for (int32 IndexA = 0; IndexA < LenA; ++IndexA)
        {
            int32 LastCount = IndexA + 1;
            for (int32 IndexB = 0; IndexB < LenB; ++IndexB)
            {
                int32 NewCount = OperationCount[IndexB];
                if (DataA[IndexA] != DataB[IndexB])
                {
                    NewCount = FMath::Min3(NewCount, LastCount, OperationCount[IndexB+1]) + 1;
                }
                OperationCount[IndexB] = LastCount;
                LastCount = NewCount;
            }
            OperationCount[LenB] = LastCount;
        }
        return OperationCount[LenB];
    }
 
} //End namespace Algo