An implementation of Levenshtein Distance algorithm in modern C++
Invalid access

There are several occurrences of out-of-range access as 1201ProgramAlarm's comment pointed out:


for (std::size_t k{ 0 }; k &lt;= size_2; ++k) costs[k] = k;

  
  

costs[j + 1]

  
  

return costs[size_2];



This problem can be fixed by increasing the size of costs by one.

Usage of the standard library


std::vector&lt;std::size_t&gt; costs(size_2);
for (std::size_t k{ 0 }; k &lt;= size_2; ++k) costs[k] = k;



Use std::iota:

std::vector&lt;std::size_t&gt; costs(size_2 + 1);
std::iota(costs.begin(), costs.end(), std::size_t{0}); // or 0_zu; see below



auto t{ upper &lt; corner ? upper : corner };
costs[j + 1] = (costs[j] &lt; t ? costs[j] : t) + 1;



Use std::min:

costs[j + 1] = std::min({upper, corner, costs[j]}) + 1;


auto

When you want the type of a variable to be deduced, auto is handy, because you don't have to write the type or expression twice.  When you want the type of a variable to be fixed, however, auto becomes cumbersome &mdash; so feel free to write

std::size_t i = 0;


An alternative is to use a user-defined literal: (there's a proposal P0330 Literal Suffix for (signed) size_t to add builtin literals for std::size_t)

namespace util_literals {
    constexpr std::size_t operator""_zu(unsigned long long number)
    {
        return static_cast&lt;std::size_t&gt;(number);
    }
}


So you can write:

using namespace util_literals;
auto i = 0_zu;


Also, instead of


for (const auto&amp; itr_1 : string_1)



it is more common to access characters by value.  Also, itr is a misleading name for characters:

for (char c_1 : string_1)


Simplification

This check is redundant:


if (size_1 == 0) return size_2;
if (size_2 == 0) return size_1;



because the algorithm works well with empty strings.



Here's my version:

#include &lt;algorithm&gt;
#include &lt;cstddef&gt;
#include &lt;iomanip&gt;
#include &lt;iostream&gt;
#include &lt;numeric&gt;
#include &lt;string&gt;
#include &lt;string_view&gt;
#include &lt;vector&gt;

std::size_t Levenshtein_distance(std::string_view string_a, std::string_view string_b)
{
    const auto size_a = string_a.size();
    const auto size_b = string_b.size();

    std::vector&lt;std::size_t&gt; distances(size_b + 1);
    std::iota(distances.begin(), distances.end(), std::size_t{0});

    for (std::size_t i = 0; i &lt; size_a; ++i) {
        std::size_t previous_distance = 0;
        for (std::size_t j = 0; j &lt; size_b; ++j) {
            distances[j + 1] = std::min({
                std::exchange(previous_distance, distances[j + 1]) + (string_a[i] == string_b[j] ? 0 : 1),
                distances[j] + 1,
                distances[j + 1] + 1
            });
        }
    }
    return distances[size_b];
}

int main()
{
    std::string string_a;
    std::string string_b;
    while (std::cin &gt;&gt; std::quoted(string_a) &gt;&gt; std::quoted(string_b)) {
        std::cout &lt;&lt; Levenshtein_distance(string_a, string_b) &lt;&lt; '\n';
    }
}


Input:

kitten sitting
corporate cooperation
123 ""
"" ""


Output:

3
5
0
0


(live demo)