Поиск слова в матрице (Word Search)

Поиск слова в матрице (Word Search)

Задача

Дана матрица букв и слово. Требуется проверить, можно ли найти слово в матрице, двигаясь по соседним ячейкам (вверх, вниз, влево, вправо). Каждую ячейку можно использовать только один раз.

Для примера:

board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]

• exist(board, "ABCCED") → True (A→B→C→C→E→D)
• exist(board, "SEE") → True (S→E→E)
• exist(board, "ABCB") → False (B повторяется)

Решение: Backtracking (DFS)

Используем глубинный поиск с возвратом (backtracking). Для каждой ячейки пробуем найти слово, рекурсивно проверяя соседей.

def exist(board, word):
    """
    Проверяет, существует ли слово в матрице.
    
    Подход:
    1. Для каждой ячейки с первой буквой слова
    2. Применяем DFS с возвратом
    3. Отмечаем посещённые ячейки, чтобы не использовать дважды
    4. Откатываем изменения при возврате
    
    Временная сложность: O(n * m * 4^L) где L — длина слова
    Пространственная сложность: O(L) для стека рекурсии
    """
    if not board or not word:
        return False
    
    rows = len(board)
    cols = len(board[0])
    visited = set()
    
    def dfs(row, col, index):
        """
        row, col — текущая позиция
        index — индекс в слове, который ищем
        """
        # Базовый случай: нашли все буквы
        if index == len(word):
            return True
        
        # Проверяем границы
        if row < 0 or row >= rows or col < 0 or col >= cols:
            return False
        
        # Проверяем, уже ли посетили эту ячейку
        if (row, col) in visited:
            return False
        
        # Проверяем, совпадает ли буква
        if board[row][col] != word[index]:
            return False
        
        # Отмечаем ячейку как посещённую
        visited.add((row, col))
        
        # Ищем следующую букву в соседних ячейках (вверх, вниз, влево, вправо)
        found = (dfs(row + 1, col, index + 1) or
                 dfs(row - 1, col, index + 1) or
                 dfs(row, col + 1, index + 1) or
                 dfs(row, col - 1, index + 1))
        
        # Откатываем изменение (backtrack)
        visited.remove((row, col))
        
        return found
    
    # Ищем начальную букву и применяем DFS
    for row in range(rows):
        for col in range(cols):
            if board[row][col] == word[0]:
                if dfs(row, col, 0):
                    return True
    
    return False

# Тестирование
board = [
    ["A","B","C","E"],
    ["S","F","C","S"],
    ["A","D","E","E"]
]

print(exist(board, "ABCCED"))  # True
print(exist(board, "SEE"))     # True
print(exist(board, "ABCB"))    # False

Оптимизация: Использование флага вместо set

Вместо хранения посещённых ячеек в set, можно изменять саму матрицу (если позволено):

def exist_optimized(board, word):
    """
    Оптимизированная версия, использующая саму матрицу для отметки.
    Экономит пространство: O(1) вместо O(n*m) для set.
    """
    if not board or not word:
        return False
    
    def dfs(row, col, index):
        if index == len(word):
            return True
        
        if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
            return False
        
        # Проверяем границу и совпадение
        if board[row][col] != word[index]:
            return False
        
        # Временно отмечаем как посещённую (изменяем значение)
        original = board[row][col]
        board[row][col] = "#"
        
        # DFS в соседних ячейках
        found = (dfs(row + 1, col, index + 1) or
                 dfs(row - 1, col, index + 1) or
                 dfs(row, col + 1, index + 1) or
                 dfs(row, col - 1, index + 1))
        
        # Восстанавливаем исходное значение
        board[row][col] = original
        
        return found
    
    for row in range(len(board)):
        for col in range(len(board[0])):
            if dfs(row, col, 0):
                return True
    
    return False

Пошаговое выполнение для "ABCCED"

board = [[A, B, C, E],
         [S, F, C, S],
         [A, D, E, E]]

Шаг 1: Находим A в (0,0), начинаем DFS
Шаг 2: word[0]=A ✓, ищем word[1]=B
  - Проверяем (1,0)=S ✗
  - Проверяем (0,1)=B ✓
Шаг 3: word[1]=B ✓, ищем word[2]=C
  - Проверяем (1,1)=F ✗
  - Проверяем (0,2)=C ✓
Шаг 4: word[2]=C ✓, ищем word[3]=C
  - Проверяем (1,2)=C ✓
Шаг 5: word[3]=C ✓, ищем word[4]=E
  - Проверяем (0,3)=E ✓
Шаг 6: word[4]=E ✓, ищем word[5]=D
  - Проверяем (2,3)=E ✗
  - Проверяем (2,2)=E ✗
  - Проверяем (1,2) уже посещён ✗
  - Откатываемся, пробуем другой путь
  - Находим (2,1)=D ✓
Шаг 7: word[5]=D ✓

Результат: True ✓

Вариант с ранней проверкой

Можно оптимизировать, проверяя существование букв заранее:

def exist_with_early_check(board, word):
    """
    Добавляем раннюю проверку: если буква не в матрице, return False.
    """
    from collections import Counter
    
    # Подсчитываем буквы в матрице
    board_chars = Counter()
    for row in board:
        for char in row:
            board_chars[char] += 1
    
    # Подсчитываем буквы в слове
    word_chars = Counter(word)
    
    # Проверяем, что все буквы есть в матрице
    for char, count in word_chars.items():
        if board_chars[char] < count:
            return False
    
    def dfs(row, col, index):
        if index == len(word):
            return True
        
        if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
            return False
        
        if board[row][col] != word[index]:
            return False
        
        original = board[row][col]
        board[row][col] = "#"
        
        found = (dfs(row + 1, col, index + 1) or
                 dfs(row - 1, col, index + 1) or
                 dfs(row, col + 1, index + 1) or
                 dfs(row, col - 1, index + 1))
        
        board[row][col] = original
        return found
    
    for row in range(len(board)):
        for col in range(len(board[0])):
            if dfs(row, col, 0):
                return True
    
    return False

Сложность анализ

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

• В худшем случае: O(n × m × 4^L), где:
  • n × m: размер матрицы
  • 4^L: в каждой позиции может быть до 4 направлений, L раз
• На практике намного быстрее благодаря pruning

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

• O(L) для стека рекурсии (глубина = длина слова)
• O(n × m) если используем set для visited
• O(1) если модифицируем матрицу

Вариант задачи: Множество слов (Word Search II)

Если нужно найти множество слов в одной матрице, используем Trie:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

def find_words(board, words):
    """
    Находит все слова из списка в матрице.
    Использует Trie для эффективного поиска.
    """
    # Строим Trie
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word
    
    result = []
    visited = set()
    
    def dfs(row, col, node):
        if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
            return
        
        if (row, col) in visited:
            return
        
        char = board[row][col]
        if char not in node.children:
            return
        
        visited.add((row, col))
        next_node = node.children[char]
        
        if next_node.word:
            result.append(next_node.word)
            next_node.word = None  # Избегаем дубликатов
        
        dfs(row + 1, col, next_node)
        dfs(row - 1, col, next_node)
        dfs(row, col + 1, next_node)
        dfs(row, col - 1, next_node)
        
        visited.remove((row, col))
    
    for row in range(len(board)):
        for col in range(len(board[0])):
            dfs(row, col, root)
    
    return result

Ключевые техники

1. Backtracking — стандартная техника для поиска с ограничениями
2. DFS (Глубинный поиск) — обход всех соседних ячеек
3. Отметка посещённых ячеек — критично для избежания циклов
4. Восстановление состояния — важный момент в backtracking
5. Trie — оптимизация для множества слов

Заключение

Это классическая задача на backtracking и DFS. Ключевые моменты:

• Используй DFS для поиска по матрице
• Отмечай посещённые ячейки
• Откатывай изменения при возврате
• Для множества слов используй Trie

Часто встречается на интервью у Google, Amazon, Microsoft.