levenshteinDistance

Returns the Levenshtein distance between s and t. The Levenshtein distance computes the minimal amount of edit operations necessary to transform s into t. Performs O(s.length * t.length) evaluations of equals and occupies O(min(s.length, t.length)) storage.

size_t levenshteinDistance(Range1 s, Range2 t)
size_t
levenshteinDistance
(
alias equals =
(
a
,
b
)
=> a == b
Range1
Range2
)
(
Range1 s
,
Range2 t
)
if (
isForwardRange!(Range1) &&
isForwardRange!(Range2)
)
size_t levenshteinDistance(Range1 s, Range2 t)

Parameters

equals: The binary predicate to compare the elements of the two ranges.
s Range1: The original range.
t Range2: The transformation target

Return Value

Type: size_t

The minimal number of edits to transform s into t.

Does not allocate GC memory.

Examples

import std.algorithm.iteration : filter;
import std.uni : toUpper;

assert(levenshteinDistance("cat", "rat") == 1);
assert(levenshteinDistance("parks", "spark") == 2);
assert(levenshteinDistance("abcde", "abcde") == 0);
assert(levenshteinDistance("abcde", "abCde") == 1);
assert(levenshteinDistance("kitten", "sitting") == 3);
assert(levenshteinDistance!((a, b) => toUpper(a) == toUpper(b))
    ("parks", "SPARK") == 2);
assert(levenshteinDistance("parks".filter!"true", "spark".filter!"true") == 2);
assert(levenshteinDistance("ID", "I♥D") == 1);

levenshteinDistance

Parameters

Return Value

Examples

Meta

Source