Good job! One question though. In cases like this when there is generally no state, isn't it better to make the methods static?
https://github.com/tdebatty/java-string-similarity/blob/mast...
The example code in README.md can probably do this instead:
MetricStringDistance msd = new Levenshtein();
System.out.println(msd.distance("My string", "My $tring"));
MetricStringDistance msd2 = new MetricLCS();
System.out.println(msd2.distance("ABDEF", "ABDIF"));Implementing mock objects which return "unexpected" results is impossible with static methods.
The standard 1 interface + 1 impl pattern in Java is just so that the Proxy.newProxyInstance can create a decorated or mocked object for testing.
So you can test the methods directly, but you can't write failure-inducing methods (like a connect exception throwing one) which test the methods which use it.