Задача: 212. Word Search II
Сложность: hard

Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.

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

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

1⃣Построение Trie:
Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже.

2⃣Запуск обхода в глубину (Backtracking) с каждой ячейки:
Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).

3⃣Обход соседних ячеек:
В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.

😎 Решение:

class TrieNode {
    var children = [Character: TrieNode]()
    var word: String? = nil
}

class Solution {
    private var board: [[Character]] = []
    private var result = [String]()

    func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
        let root = TrieNode()
        for word in words {
            var node = root
            for letter in word {
                if node.children[letter] == nil {
                    node.children[letter] = TrieNode()
                }
                node = node.children[letter]!
            }
            node.word = word
        }

        self.board = board
        for row in 0..<board.count {
            for col in 0..<board[0].count {
                if root.children[board[row][col]] != nil {
                    backtracking(row, col, root)
                }
            }
        }

        return result
    }

    private func backtracking(_ row: Int, _ col: Int, _ parent: TrieNode) {
        let letter = board[row][col]
        guard let currNode = parent.children[letter] else { return }

        if let word = currNode.word {
            result.append(word)
            currNode.word = nil
        }

        board[row][col] = "#"

        let rowOffset = [-1, 0, 1, 0]
        let colOffset = [0, 1, 0, -1]
        for i in 0..<4 {
            let newRow = row + rowOffset[i]
            let newCol = col + colOffset[i]
            if newRow >= 0, newRow < board.count, newCol >= 0, newCol < board[0].count, currNode.children[board[newRow][newCol]] != nil {
                backtracking(newRow, newCol, currNode)
            }
        }

        board[row][col] = letter

        if currNode.children.isEmpty {
            parent.children[letter] = nil
        }
    }
}

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