View source code
Display the source code in std/algorithm/comparison.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

Function std.algorithm.comparison.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 Ο(s.length * t.length) evaluations of equals and occupies Ο(min(s.length, t.length)) storage.

size_t levenshteinDistance(alias equals, Range1, Range2) (
  Range1 s,
  Range2 t
)
if (isForwardRange!Range1 && isForwardRange!Range2);

size_t levenshteinDistance(alias equals, Range1, Range2) (
  auto ref Range1 s,
  auto ref Range2 t
)
if (isConvertibleToString!Range1 || isConvertibleToString!Range2);

Parameters

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

Returns

The minimal number of edits to transform s into t.

Does not allocate GC memory.

Example

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

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

Authors

Andrei Alexandrescu

License

Boost License 1.0.