Keyboard Row

https://leetcode.com/problems/keyboard-rowEasy

Условие

Дан массив строк words. Нужно вернуть массив, содержащий только те слова, которые можно напечатать, используя буквы только одной строки клавиатуры. На стандартной QWERTY-клавиатуре строки расположены следующим образом:

• Первая строка: “qwertyuiop”

• Вторая строка: “asdfghjkl”

• Третья строка: “zxcvbnm”

Каждое слово в массиве words состоит из латинских букв (и может быть как в верхнем, так и в нижнем регистре).

Примеры

Input: words = [“Hello”, “Alaska”, “Dad”, “Peace”]

Output: [“Alaska”, “Dad”]
Input: words = ["omk"]

Output: []
Input: words = ["adsdf", "sfd"]

Output: ["adsdf", "sfd"]

Решение

fun findWords(words: Array<String>): Array<String> {
    // Множества символов для каждой строки клавиатуры
    val row1 = setOf('q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p')
    val row2 = setOf('a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l')
    val row3 = setOf('z', 'x', 'c', 'v', 'b', 'n', 'm')

    val result = mutableListOf<String>()

    for (word in words) {
        val lowercaseWord = word.lowercase()  // Приводим слово к нижнему регистру
        val row = when (lowercaseWord[0]) {  // Определяем, к какой строке принадлежит первая буква
            in row1 -> row1
            in row2 -> row2
            else -> row3
        }

        // Проверяем, что все символы слова находятся в одной строке клавиатуры
        if (lowercaseWord.all { it in row }) {
            result.add(word)
        }
    }

    return result.toTypedArray()
}

Временная сложность

O(n * m), где n — количество слов, а m — длина самого длинного слова, так как мы проверяем каждое слово и его символы.

Пространственная сложность

O(n), так как результат содержит отфильтрованные слова.