(String s, String t, int sLen, int tLen)
| 188 | } |
| 189 | |
| 190 | private static int getDistance(String s, String t, int sLen, int tLen) { |
| 191 | // compute the Levenshtein Distance |
| 192 | // https://en.wikipedia.org/wiki/Levenshtein_distance |
| 193 | |
| 194 | // degenerate cases |
| 195 | if (s.equals(t)) return 0; |
| 196 | if (sLen == 0) return tLen; |
| 197 | if (tLen == 0) return sLen; |
| 198 | |
| 199 | // create two work vectors of integer distances |
| 200 | int[] v0 = new int[tLen+1]; |
| 201 | int[] v1 = new int[tLen+1]; |
| 202 | |
| 203 | // initialize v0 (the previous row of distances) |
| 204 | // this row is A[0][i]: edit distance for an empty s |
| 205 | // the distance is just the number of characters to delete from t |
| 206 | for (int i=0; i<=tLen; ++i) { |
| 207 | v0[i] = i; |
| 208 | } |
| 209 | |
| 210 | for (int i=0; i<sLen; ++i) { |
| 211 | // calculate v1 (current row distances) from the previous row v0 |
| 212 | |
| 213 | // first element of v1 is A[i+1][0] |
| 214 | // edit distance is delete (i+1) chars from s to match empty t |
| 215 | |
| 216 | v1[0] = i+1; |
| 217 | |
| 218 | for (int j=0; j<tLen; ++j) { |
| 219 | v1[j+1] = min3(v1[j ]+1, |
| 220 | v0[j+1]+1, |
| 221 | v0[j ]+(s.charAt(i) == t.charAt(j) ? 0 : 1)); |
| 222 | } |
| 223 | |
| 224 | // copy v1 (current row) to v0 (previous row) for next iteration |
| 225 | System.arraycopy(v1, 0, v0, 0, tLen); |
| 226 | } |
| 227 | |
| 228 | return v1[tLen]; |
| 229 | } |
| 230 | |
| 231 | private static int getDistance(byte[] s, byte[] t, int sLen, int tLen) { |
| 232 | // degenerate cases |
no test coverage detected