LeetCode Entry

648. Replace Words

07.06.2024 medium 2024 kotlin rust

Replace words with suffixes from dictionary

648. Replace Words medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/632

Problem TLDR

Replace words with suffixes from dictionary #medium #trie

Intuition

Walk through the word and check if the suffix is in the dictionary. To speed up this we can use a HashMap or a Trie.

Approach

Let’s use both HashMap and Trie. HashMap code is shorter but slower.

Complexity

• Time complexity: \(O(n)\), O(nw^2) for HashMap solution, as we rebuilding each suffix in the word of w length

• Space complexity: \(O(d + w)\)

Code

    fun replaceWords(dictionary: List<String>, sentence: String): String {
        class Trie(var word: Int = -1): HashMap<Char, Trie>()
        val trie = Trie()
        for ((i, r) in dictionary.withIndex()) {
            var t = trie
            for (c in r) t = t.getOrPut(c) { Trie() }
            t.word = i
        }
        return sentence.split(" ").map {
            var t = trie
            for (c in it) {
                if (t.word >= 0) break
                t = t[c] ?: break
            }
            dictionary.getOrNull(t.word) ?: it
        }.joinToString(" ")
    }

    pub fn replace_words(dictionary: Vec<String>, sentence: String) -> String {
        let set = dictionary.into_iter().collect::<HashSet<_>>();
        sentence.split(" ").map(|s| {
            let mut w = String::new();
            for c in s.chars() {
                w.push(c);
                if set.contains(&w) { break }
            }; w
        }).collect::<Vec<_>>().join(" ")
    }