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.levenshteinDistanceAndPath

Returns the Levenshtein distance and the edit path between s and t.

Tuple!(size_t,EditOp[]) levenshteinDistanceAndPath(alias equals, Range1, Range2) (
  Range1 s,
  Range2 t
)
if (isForwardRange!Range1 && isForwardRange!Range2);

Tuple!(size_t,EditOp[]) levenshteinDistanceAndPath(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

Tuple with the first element being the minimal amount of edits to transform s into t and the second element being the sequence of edits to effect this transformation.

Allocates GC memory for the returned EditOp[] array.

Example

string a = "Saturday", b = "Sundays";
auto p = levenshteinDistanceAndPath(a, b);
writeln(p[0]); // 4
assert(equal(p[1], "nrrnsnnni"));

Authors

Andrei Alexandrescu

License

Boost License 1.0.