Alternative solution for https://www.facebook.com/Engineering/videos/10152735777427200/ which give complexity O(n^3)

NearbyWordsAlt.kt

package NearbyWordsAlt

import kotlin.collections.HashSet

fun main(args : Array<String>) {
    println(nearbyWords("gi"))
}

fun getAllWordPermutations(word: String): Set<String> {

    val word_end = word.length-1
    var permutations = setOf("")
    
    for(i in word_end downTo 0) {
        val nearby_chars = getNearbyChar(word[i])
        val sub_words = HashSet<String>()

        nearby_chars.forEach { char ->
            permutations.forEach {
                sub_words.add("$char$it")
            }
        }
        permutations = sub_words
    }

    return permutations
}

//simulating helper function
fun getNearbyChar(char: Char): Set<Char> {
    return HashSet<Char>().apply {
        when(char) {
            'g' -> addAll(arrayListOf('g', 'h', 'f'))
            'i' -> addAll(arrayListOf('i', 'o', 'k'))
        }
    }
}

//simulating helper function
fun isWord(word: String) : Boolean {    
  return (word == "go" || word == "hi")
}