Задача: 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 {
    public $children;
    public $word;

    public function __construct() {
        $this->children = [];
        $this->word = null;
    }
}

class Solution {
    private $board;
    private $result;

    public function findWords($board, $words) {
        $root = $this->buildTrie($words);
        $this->board = $board;
        $this->result = [];

        for ($row = 0; $row < count($board); ++$row) {
            for ($col = 0; $col < count($board[0]); ++$col) {
                if (isset($root->children[$board[$row][$col]])) {
                    $this->backtrack($row, $col, $root);
                }
            }
        }
        return $this->result;
    }

    private function buildTrie($words) {
        $root = new TrieNode();
        foreach ($words as $word) {
            $node = $root;
            for ($i = 0; $i < strlen($word); ++$i) {
                $letter = $word[$i];
                if (!isset($node->children[$letter])) {
                    $node->children[$letter] = new TrieNode();
                }
                $node = $node->children[$letter];
            }
            $node->word = $word;
        }
        return $root;
    }

    private function backtrack($row, $col, $parent) {
        $letter = $this->board[$row][$col];
        $currNode = $parent->children[$letter];

        if ($currNode->word !== null) {
            $this->result[] = $currNode->word;
            $currNode->word = null;
        }

        $this->board[$row][$col] = '#';

        $rowOffset = [-1, 0, 1, 0];
        $colOffset = [0, 1, 0, -1];
        for ($i = 0; $i < 4; ++$i) {
            $newRow = $row + $rowOffset[$i];
            $newCol = $col + $colOffset[$i];
            if (
                $newRow >= 0 && $newRow < count($this->board) &&
                $newCol >= 0 && $newCol < count($this->board[0])
            ) {
                if (isset($currNode->children[$this->board[$newRow][$newCol]])) {
                    $this->backtrack($newRow, $newCol, $currNode);
                }
            }
        }

        $this->board[$row][$col] = $letter;

        if (empty($currNode->children)) {
            unset($parent->children[$letter]);
        }
    }
}

// Example usage:
$solution = new Solution();
$board = [
    ['o', 'a', 'a', 'n'],
    ['e', 't', 'a', 'e'],
    ['i', 'h', 'k', 'r'],
    ['i', 'f', 'l', 'v']
];
$words = ["oath", "pea", "eat", "rain"];
print_r($solution->findWords($board, $words));

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