Last active
March 5, 2024 10:53
-
-
Save ademar111190/34d3de41308389a0d0d8 to your computer and use it in GitHub Desktop.
Levenshtein Distance algorithm implementation using Kotlin
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import kotlin.math.min | |
fun levenshtein(lhs : CharSequence, rhs : CharSequence) : Int { | |
if(lhs == rhs) { return 0 } | |
if(lhs.isEmpty()) { return rhs.length } | |
if(rhs.isEmpty()) { return lhs.length } | |
val lhsLength = lhs.length + 1 | |
val rhsLength = rhs.length + 1 | |
var cost = Array(lhsLength) { it } | |
var newCost = Array(lhsLength) { 0 } | |
for (i in 1..rhsLength-1) { | |
newCost[0] = i | |
for (j in 1..lhsLength-1) { | |
val match = if(lhs[j - 1] == rhs[i - 1]) 0 else 1 | |
val costReplace = cost[j - 1] + match | |
val costInsert = cost[j] + 1 | |
val costDelete = newCost[j - 1] + 1 | |
newCost[j] = min(min(costInsert, costDelete), costReplace) | |
} | |
val swap = cost | |
cost = newCost | |
newCost = swap | |
} | |
return cost[lhsLength - 1] | |
} |
Use the GPT one so then you can include "AI" in your app name and win $$$
Seriously you can benchmark them if you want 😊 I presume the human one is better for RAM as it's only 2 arrays instead of a 2d arrays, but yours should be better for cpu I guess?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I used the code for Levenshtein distance method from above but also asked ChatGPT to write me one. Now I'm thinking which one should I pick 🤔 😅
The human-written one is (more) readable.
And both pass the test from @Wavesonics (thanks for that one! 👍 ).