Grzegorz.Poreba.73
BAN USERWhole idea is instead of for every string check every other string and check if they are off by one O(n^2 m) we for every string delete one character from string and remember it. If it already has been remembered, it means that there are 2 string off by one in array. This however takes O(nm^2) due to the fact that for every letter in string we create a string without that letter, and this requires us to copy every remaining letter. To combat that, we instead of creating a string, use a rolling hash. For each string we calculate a rolling hash and then for each letter in string we calculate "partlyHash" which is equal to hash minus hash part of current letter (which is 128^(m - letterIndex - 1)). Then we store this by its hash in `partlyHashToString`. There is a chance that there are collisions so we store strings and then double check if it is different by one for sure. This makes this algorithm O(n*m)
fun isPairWithDiffByOne(input: Array<String>): Boolean {
// map for storing whole strings to hash of them without one of the letters
val partlyHashToString = HashMap<Int, ArrayList<String>>()
for (string in input) {
// rolling hash for letters
var wholeHash = 0
// variable for calculating 128 ^ letters - 1, so in next loop we can easily use that in subtraction
var rolled128 = 1
for (letter in string) {
wholeHash = 128 * wholeHash + letter.code
rolled128 *= 128
}
rolled128 /= 128
for (letter in string) {
// from rolling hash we subtract rolling part of letter
val partlyHash = wholeHash - (rolled128 * letter.code)
val valuesForPartlyHash = partlyHashToString[partlyHash] ?: ArrayList()
partlyHashToString[partlyHash] = valuesForPartlyHash
// if array is not empty there is a string which without one of its letter has the same hash as our partlyHash
if (valuesForPartlyHash.isNotEmpty()) {
// to be safe if there are hash collisions we check to be sure that those strings are in fact off by one
// its highly improbable due to high rolling constant = 128, however hash value is constantly rolling over Int.MAX_VALUE
// so there might be a case when hashes collide
val isAMatch = valuesForPartlyHash.any { isByOne(it, string) }
if (isAMatch)
return true
}
valuesForPartlyHash.add(string)
rolled128 /= 128
}
}
return false
}
// failsafe for collisions
fun isByOne(first: String, second: String): Boolean {
var alreadyModified = false
for (i in first.indices) {
if (first[i] != second[i]) {
if (alreadyModified)
return false
alreadyModified = true
}
}
return true
}
Code is written in kotlin
- Grzegorz.Poreba.73 July 30, 2022