EditDistance { public static int optimalAlignment(@NotNull CharSequence str1, @NotNull CharSequence str2, boolean caseSensitive) { int[][] d = prepare(str1.length(), str2.length()); for (int i = 1; i <= str1.length(); i++) { for (int j = 1; j <= str2.length(); j++) { int cost = equal(str1.charAt(i - 1), str2.charAt(j - 1), caseSensitive) ? 0 : 1; d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost); if (i > 1 && j > 1 && equal(str1.charAt(i - 1), str2.charAt(j - 2), caseSensitive) && equal(str1.charAt(i - 2), str2.charAt(j - 1), caseSensitive)) { d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost); } } } return d[str1.length()][str2.length()]; } private  EditDistance(); static int levenshtein(@NotNull CharSequence str1, @NotNull CharSequence str2, boolean caseSensitive); static int optimalAlignment(@NotNull CharSequence str1, @NotNull CharSequence str2, boolean caseSensitive);  }
@Test public void optimalAlignment() { assertEquals(1, EditDistance.optimalAlignment("ab", "ba", true)); assertEquals(2, EditDistance.optimalAlignment("AB", "ba", true)); assertEquals(3, EditDistance.optimalAlignment("ca", "abc", true)); assertEquals(3, EditDistance.optimalAlignment("Ca", "abc", true)); }
@Test public void optimalAlignmentCaseInsensitive() { assertEquals(1, EditDistance.optimalAlignment("ab", "ba", false)); assertEquals(1, EditDistance.optimalAlignment("AB", "ba", false)); assertEquals(3, EditDistance.optimalAlignment("ca", "abc", false)); assertEquals(3, EditDistance.optimalAlignment("Ca", "abc", false)); }