Word Pattern

Условие

Дана строка pattern и строка s, необходимо определить, следует ли строка s такому же шаблону, как и pattern. Шаблон должен соответствовать каждому слову в строке, и каждый символ в шаблоне должен соответствовать одному слову.

Примеры

Input: pattern = “abba”, s = “dog cat cat dog”

Output: true

Explanation:

‘a’ соответствует “dog”.
‘b’ соответствует “cat”.

Input: pattern = “abba”, s = “dog cat cat fish”

Output: false

Input: pattern = “aaaa”, s = “dog cat cat dog”

Output: false

Решение

fun wordPattern(pattern: String, s: String): Boolean {
    val words = s.split(" ") // Разделяем строку на слова
    if (pattern.length != words.size) return false // Проверяем количество слов

    val charToWord = mutableMapOf<Char, String>() // Сопоставление символов и слов
    val wordToChar = mutableMapOf<String, Char>() // Сопоставление слов и символов

    for (i in pattern.indices) {
        val char = pattern[i]
        val word = words[i]

        // Проверяем, есть ли несоответствие между символом и словом
        if (charToWord[char] != null && charToWord[char] != word || wordToChar[word] != null && wordToChar[word] != char) {
            return false
        }

        // Сопоставляем символ слову и слово символу
        charToWord[char] = word
        wordToChar[word] = char
    }

    return true // Если все символы соответствуют словам, возвращаем true
}

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

O(n), где n — длина строки pattern или количество слов в s.

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

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