LeetCode 2452. Слова в двух редакциях словаря

Примечания LeetCode [53]: ✅✅✅ Решение Kotlin без Trie — объяснение || Очень просто и легко понять

Проблема

Интуиция

1. Перебрать queries.
2. Для каждого query выполните цикл по dictionary
3. Подсчитайте количество разных символов между query и word из dictionary.
4. Если количество различных символов равно или меньше 2, добавьте его в список result.

Выполнение

class Solution {
    fun twoEditWords(queries: Array<String>, dictionary: Array<String>): List<String> {
        val result = mutableListOf<String>()
        for (i in queries.indices) {
            val query = queries[i]
            for (j in dictionary.indices) {
                val word = dictionary[j]
                var count = 0
                for (k in word.indices) {
                    if (count > 2) break
                    if (query[k] != word[k]) {
                        count++
                    }
                }
                if (count <= 2) {
                    result.add(query)
                    break
                }
            }
        }
        return result
    }
}

Анализ сложности

• Временная сложность: O(queries.length *dictionary.length * n)
• Сложность пространства: O(1)

Похожие вопросы