Display the source code in std/algorithm/comparison.d from which this page was generated on github.

If you spot a problem with this page, click here to create a Bugzilla issue.

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

Name	Description
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.