1258. Synonymous Sentences

You are given a list of equivalent string pairs synonyms where synonyms[i] = [si, ti] indicates that si and ti are equivalent strings. You are also given a sentence text.

Return all possible synonymous sentences sorted lexicographically.

kotlin

class Solution {
    val mp = mutableMapOf<String, String>()
    val gr = mutableMapOf<String, List<String>>()
    val res = mutableListOf<String>()

    fun find(str: String) : String {
        if(mp.containsKey(str)) {
            return __find(str)
        }
        mp[str] = str
        return mp[str]!!
    }
    fun __find(str: String): String {
        return if(mp[str] == str) str else {
            mp[str] = __find(mp[str]!!)
            return mp[str]!!
        };
    }
    fun uni(str1: String, str2: String) {
        val ps1 = find(str1)
        val ps2 = find(str2)
        if(ps1 > ps2) {
            mp[ps1] = ps2;
        } else {
            mp[ps2] = ps1;
        }
    }
    fun backTracking(tokens : List<String>, selected : MutableList<String>, i : Int) {
        if(i == tokens.size) {
            res.add(selected.joinToString(" "))
        } else {
            for(s in gr[tokens[i]]!!) {
                selected.add(s)
                backTracking(tokens, selected, i + 1)
                selected.removeAt(i)
            }
        }
    }
    fun generateSentences(synonyms: List<List<String>>, text: String): List<String> {
        val token = text.split(' ');
        token.forEach{t -> find(t)};
        synonyms.forEach{sy -> uni(sy[0], sy[1])}
        val tmp = mp.asSequence().groupBy({find(it.key)}, {it.key})
        token.forEach{t ->
            val key = find(t)
            val value = tmp[key]!!
            gr[t] = value.sorted()
        }
        val tmp2 = mutableListOf<String>()
        backTracking(token, tmp2, 0)
        return res;
    }
}