int (@NotNull CharSequence str1, @NotNull CharSequence str2, boolean caseSensitive, int limit) { if (str1.length() > str2.length()) { @NotNull CharSequence tmp = str1; str1 = str2; str2 = tmp; } final int length1 = str1.length(); final int length2 = str2.length(); if (length1 == 0) { return length2; } else if (length2 == 0) { return length1; } int[] v0 = new int[length1 + 1]; int[] v1 = new int[length1 + 1]; int[] v2 = new int[length1 + 1];// three rows of length n + 1 instead of n*m two dimensional array for (int i = 1; i <= length1; i++) v1[i] = i; int minCost = limit + 1; // flip to negative on MAX_INT doesn't matter for (int j = 0; j < length2; j++) { v2[0] = j + 1; for (int i = 0; i < length1; i++) { final int cost = equal(str1.charAt(i), str2.charAt(j), caseSensitive) ? 0 : 1; v2[i + 1] = min(v2[i] + 1, // insertion v1[i + 1] + 1, // deletion v1[i] + cost); // substitution (replacement) if(i > 0 && j > 0 && equal(str2.charAt(j), str1.charAt(i - 1), caseSensitive) && equal(str1.charAt(i), str2.charAt(j - 1), caseSensitive)) { // transposition (swap) v2[i + 1] = Math.min(v2[i + 1], v0[i - 1] + cost); } final int currentCost = v2[i + 1]; if (currentCost < minCost) { minCost = currentCost; } } if (minCost > limit) { return minCost; } minCost = limit + 1; int[] temp = v0; v0 = v1; v1 = v2; v2 = temp; // will be overwritten/reused } // our last action in the loop above was to switch arrays, // so v1 has the most recent cost counts return v1[length1]; }