Why does indexing a string inside of a recursive call yield a different result?

Adnan relay.public.adnan at outlook.com
Sun May 10 10:02:18 UTC 2020



In my naive implementation of edit-distance finder, I have to 
check whether the last characters of two strings match:

ulong editDistance(const string a, const string b) {
     if (a.length == 0)
         return b.length;
     if (b.length == 0)
         return a.length;

     const auto delt = a[$ - 1] == b[$ - 1] ? 0 : 1;

     import std.algorithm : min;

     return min(
         editDistance(a[0 .. $ - 1], b[0 .. $ - 1]) + delt,
         editDistance(a, b[0 .. $ - 1]) + 1,
         editDistance(a[0 .. $ - 1], b) + 1
     );
}

This yields the expected results but if I replace delt with its 
definition it always returns 1 on non-empty strings:

ulong editDistance(const string a, const string b) {
     if (a.length == 0)
         return b.length;
     if (b.length == 0)
         return a.length;

     //const auto delt = a[$ - 1] == b[$ - 1] ? 0 : 1;

     import std.algorithm : min;

     return min(
         editDistance(a[0 .. $ - 1], b[0 .. $ - 1]) + a[$ - 1] == 
b[$ - 1] ? 0 : 1, //delt,
         editDistance(a, b[0 .. $ - 1]) + 1,
         editDistance(a[0 .. $ - 1], b) + 1
     );
}

Why does this result change?



More information about the Digitalmars-d-learn mailing list