Задача: 269. Alien Dictionary
Сложность: hard

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

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

👨‍💻 Алгоритм:

1⃣Извлечение отношений порядка и создание списков смежности:
Извлечь отношения порядка между буквами из слов.
Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого.

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

import java.util.*

class Solution {
    fun alienOrder(words: Array<String>): String {
        val adjList = mutableMapOf<Char, MutableSet<Char>>()
        val inDegree = mutableMapOf<Char, Int>()

        for (word in words) {
            for (char in word) {
                inDegree[char] = 0
            }
        }

        for ((firstWord, secondWord) in words.zip(words.drop(1))) {
            for ((c, d) in firstWord.zip(secondWord)) {
                if (c != d) {
                    if (d !in adjList.getOrDefault(c, mutableSetOf())) {
                        adjList.getOrPut(c) { mutableSetOf() }.add(d)
                        inDegree[d] = inDegree.getOrDefault(d, 0) + 1
                    }
                    break
                }
            }
            if (secondWord.length < firstWord.length && firstWord.startsWith(secondWord)) {
                return ""
            }
        }

        val output = mutableListOf<Char>()
        val queue: Queue<Char> = LinkedList()

        for ((char, degree) in inDegree) {
            if (degree == 0) {
                queue.add(char)
            }
        }

        while (queue.isNotEmpty()) {
            val c = queue.poll()
            output.add(c)
            for (d in adjList.getOrDefault(c, emptySet())) {
                inDegree[d] = inDegree[d]!! - 1
                if (inDegree[d] == 0) {
                    queue.add(d)
                }
            }
        }

        if (output.size < inDegree.size) {
            return ""
        }

        return output.joinToString("")
    }
}

Ставь 👍 и забирай 📚 Базу знаний

📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 79. Word Search
Сложность: medium

Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.

Слово можно составить из букв последовательно смежных ячеек, где смежные ячейки находятся рядом по горизонтали или вертикали. Одна и та же ячейка с буквой не может быть использована более одного раза.

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

👨‍💻 Алгоритм:

1⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки.

2⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова.

3⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования.

😎 Решение:

class Solution {
    lateinit var board: Array<CharArray>
    var ROWS: Int = 0
    var COLS: Int = 0

    fun exist(board: Array<CharArray>, word: String): Boolean {
        this.board = board
        ROWS = board.size
        COLS = board[0].size

        for (row in 0 until ROWS) {
            for (col in 0 until COLS) {
                if (backtrack(row, col, word, 0)) {
                    return true
                }
            }
        }
        return false
    }

    private fun backtrack(row: Int, col: Int, word: String, index: Int): Boolean {
        if (index == word.length) return true
        if (row < 0 || row == ROWS || col < 0 || col == COLS || board[row][col] != word[index]) return false

        board[row][col] = '#'
        val result = (backtrack(row + 1, col, word, index + 1) ||
                      backtrack(row - 1, col, word, index + 1) ||
                      backtrack(row, col + 1, word, index + 1) ||
                      backtrack(row, col - 1, word, index + 1))
        board[row][col] = word[index]
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний