private static int _getDistance111 ( @ Nonnull final char [ ] aStr1 , @ Nonnegative final int nLen1 , @ Nonnull final char [ ] aStr2 , @ Nonnegative final int nLen2 ) { // previous cost array, horizontally int [ ] aPrevRow = new int [ nLen1 + 1 ] ; // cost array, horizontally int [ ] aCurRow = new int [ nLen1 + 1 ] ; // init for ( int i = 0 ; i <= nLen1 ; i ++ ) aPrevRow [ i ] = i ; for ( int j = 0 ; j < nLen2 ; j ++ ) { final int ch2 = aStr2 [ j ] ; aCurRow [ 0 ] = j + 1 ; for ( int i = 0 ; i < nLen1 ; i ++ ) { final int nSubstVal = aStr1 [ i ] == ch2 ? 0 : 1 ; aCurRow [ i + 1 ] = Math . min ( Math . min ( aCurRow [ i ] + 1 , aPrevRow [ i + 1 ] + 1 ) , aPrevRow [ i ] + nSubstVal ) ; } // swap current distance counts to 'previous row' distance counts final int [ ] tmp = aPrevRow ; aPrevRow = aCurRow ; aCurRow = tmp ; } // our last action in the above loop was to switch d and p, so p now // actually has the most recent cost counts return aPrevRow [ nLen1 ] ; }
Main generic Levenshtein implementation that uses 1 for all costs!