Условие

В некотором инопланетном языке используются английские строчные буквы, но, возможно, в другом порядке. Вам дан массив слов words, написанных на этом языке, и строка order, представляющая порядок алфавита. Требуется определить, отсортированы ли слова в массиве words лексикографически в соответствии с данным порядком алфавита.

Примеры

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz” Output: true Explanation: Поскольку 'h' предшествует 'l' в данном языке, последовательность слов отсортирована.

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz” Output: false Explanation: Поскольку 'd' следует после 'l' в данном языке, слова[0] > слова[1], следовательно, последовательность не отсортирована.

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz” Output: false Explanation: Первые три символа "app" совпадают, но вторая строка короче. Согласно лексикографическим правилам, "apple" > "app", потому что 'l' > '∅', где '∅' обозначает пустой символ, который меньше любого другого символа.

Решение

fun isAlienSorted(words: Array<String>, order: String): Boolean {
    // Создаем массив для хранения индексов символов в новом алфавитном порядке
    val index = IntArray(26)
    for (i in order.indices) {
        index[order[i] - 'a'] = i
    }

    // Функция для сравнения двух слов в соответствии с новым порядком
    fun isOrdered(word1: String, word2: String): Boolean {
        val len1 = word1.length
        val len2 = word2.length
        val minLen = minOf(len1, len2)
        for (i in 0 until minLen) {
            val char1 = word1[i]
            val char2 = word2[i]
            if (char1 != char2) {
                return index[char1 - 'a'] < index[char2 - 'a']
            }
        }
        return len1 <= len2
    }

    // Проверяем каждую пару соседних слов
    for (i in 0 until words.size - 1) {
        if (!isOrdered(words[i], words[i + 1])) {
            return false
        }
    }
    return true
}

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

O(C), где C — общее количество символов во всех словах.

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

O(1), поскольку используется фиксированный дополнительный массив размером 26 для хранения индексов символов.