Поиск слова: разбор задачи

Почему эта задача важна?

Задача "Поиск слова" позволяет оценить:

• 🧠 Умение работать с двумерными структурами данных
• ⚡ Навыки применения алгоритмов поиска в глубину (DFS)
• 🎯 Понимание принципов бэктрекинга и отслеживания посещенных состояний
• 🔍 Способность оптимизировать алгоритм для улучшения производительности

Постановка задачи

Формулировка:

Дана двумерная сетка символов board и строка word. Верните true, если слово присутствует в сетке, иначе верните false.

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

Примеры:

// Первый пример ✅
Input:
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "CAT"
Output: true
Объяснение: Слово "CAT" можно составить, начиная с "C" в верхней строке, 
затем двигаясь вниз к "A" в третьей строке, и затем вправо к "T".

// Второй пример ✅
Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
],
word = "ABCCED"
Output: true

// Третий пример ❌
Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
],
word = "ABCB"
Output: false
Объяснение: Буква "B" использована дважды.

Ограничения:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board и word состоят только из строчных и заглавных английских букв

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Поиск в глубину (DFS) с бэктрекингом 🔍

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  
  // Вспомогательная функция для DFS
  function dfs(r, c, index) {
    // Базовый случай: все символы слова найдены
    if (index === word.length) {
      return true;
    }
    
    // Проверка границ и соответствия текущего символа
    if (
      r < 0 || r >= rows || 
      c < 0 || c >= cols || 
      board[r][c] !== word[index]
    ) {
      return false;
    }
    
    // Сохраняем текущий символ и временно помечаем ячейку как посещенную
    const temp = board[r][c];
    board[r][c] = '#'; // Используем специальный символ для отметки
    
    // Проверяем четыре направления: вверх, вправо, вниз, влево
    const found = 
      dfs(r + 1, c, index + 1) || 
      dfs(r, c + 1, index + 1) || 
      dfs(r - 1, c, index + 1) || 
      dfs(r, c - 1, index + 1);
    
    // Восстанавливаем исходный символ (бэктрекинг)
    board[r][c] = temp;
    
    return found;
  }
  
  // Перебираем все возможные начальные позиции
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) {
        return true;
      }
    }
  }
  
  return false;
}

Анализ решения:

✅ Эффективно находит слово, если оно существует

✅ Использует доску как маркер посещенных ячеек (экономит память)

✅ Временная сложность O(M × N × 4^L), где M×N - размер доски, L - длина слова

❌ В худшем случае может быть медленным из-за экспоненциальной зависимости от длины слова

Решение 2: DFS с отдельной матрицей для отслеживания посещенных ячеек 🚀

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  
  // Матрица для отслеживания посещенных ячеек
  const visited = Array(rows).fill().map(() => Array(cols).fill(false));
  
  function dfs(r, c, index) {
    if (index === word.length) {
      return true;
    }
    
    if (
      r < 0 || r >= rows || 
      c < 0 || c >= cols || 
      visited[r][c] || 
      board[r][c] !== word[index]
    ) {
      return false;
    }
    
    // Помечаем ячейку как посещенную
    visited[r][c] = true;
    
    // Проверяем четыре направления
    const found = 
      dfs(r + 1, c, index + 1) || 
      dfs(r, c + 1, index + 1) || 
      dfs(r - 1, c, index + 1) || 
      dfs(r, c - 1, index + 1);
    
    // Снимаем метку посещения (бэктрекинг)
    visited[r][c] = false;
    
    return found;
  }
  
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) {
        return true;
      }
    }
  }
  
  return false;
}

Характеристики:

✅ Более прямолинейная реализация с явной матрицей посещений

✅ Не изменяет исходную доску (полезно, если нужно сохранить исходные данные)

❌ Требует дополнительной памяти O(M × N) для матрицы посещений

❌ Та же временная сложность O(M × N × 4^L)

Решение 3: Оптимизированный DFS с предварительными проверками 🔧

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  
  // Предварительная проверка: подсчет символов в доске и слове
  const charCount = {};
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const char = board[r][c];
      charCount[char] = (charCount[char] || 0) + 1;
    }
  }
  
  // Проверяем, хватает ли символов на доске для составления слова
  for (const char of word) {
    if (!charCount[char]) {
      return false;
    }
    charCount[char]--;
    if (charCount[char] < 0) {
      return false;
    }
  }
  
  // Начинаем с первого символа слова, чтобы ускорить поиск
  const firstChar = word[0];
  const startPositions = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === firstChar) {
        startPositions.push([r, c]);
      }
    }
  }
  
  // Если первый символ не найден, слово не может быть составлено
  if (startPositions.length === 0) {
    return false;
  }
  
  // Массив направлений для более компактной записи
  const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]];
  
  function dfs(r, c, index) {
    if (index === word.length) {
      return true;
    }
    
    if (
      r < 0 || r >= rows || 
      c < 0 || c >= cols || 
      board[r][c] !== word[index]
    ) {
      return false;
    }
    
    const temp = board[r][c];
    board[r][c] = '#';
    
    // Используем массив направлений
    for (const [dr, dc] of directions) {
      if (dfs(r + dr, c + dc, index + 1)) {
        return true;
      }
    }
    
    board[r][c] = temp;
    return false;
  }
  
  // Проверяем только позиции, где есть первый символ слова
  for (const [r, c] of startPositions) {
    if (dfs(r, c, 0)) {
      return true;
    }
  }
  
  return false;
}

Преимущества и недостатки:

✅ Оптимизация за счет предварительной проверки символов

✅ Поиск начинается только с позиций, где есть первый символ слова

✅ Компактная запись направлений с помощью массива

❌ Более сложная реализация

❌ Дополнительная предварительная обработка может быть излишней для небольших входных данных

Решение 4: Итеративный подход с использованием стека 📊

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]];
  
  // Стек для DFS: [строка, столбец, индекс в слове, посещенные ячейки]
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === word[0]) {
        const visited = new Set([`${r},${c}`]);
        const stack = [[r, c, 0, visited]];
        
        while (stack.length > 0) {
          const [row, col, index, vis] = stack.pop();
          
          // Если нашли все символы слова
          if (index === word.length - 1) {
            return true;
          }
          
          // Проверяем соседние ячейки
          for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = `${newRow},${newCol}`;
            
            if (
              newRow >= 0 && newRow < rows &&
              newCol >= 0 && newCol < cols &&
              !vis.has(key) &&
              board[newRow][newCol] === word[index + 1]
            ) {
              // Создаем новую копию множества посещенных ячеек
              const newVis = new Set(vis);
              newVis.add(key);
              
              stack.push([newRow, newCol, index + 1, newVis]);
            }
          }
        }
      }
    }
  }
  
  return false;
}

Особенности:

✅ Избегает ограничений стека вызовов, присущих рекурсии

✅ Может быть более понятным для разработчиков, предпочитающих итеративный подход

❌ Менее эффективен по памяти из-за необходимости хранить копии множеств посещенных ячеек

❌ Более сложная реализация по сравнению с рекурсивным подходом

Интуиция за алгоритмом

Ключевая идея алгоритма заключается в следующем:

1. Для каждой ячейки в сетке, которая содержит первую букву искомого слова, мы начинаем поиск в глубину.
2. На каждом шаге мы помечаем текущую ячейку как посещенную, чтобы избежать повторного использования.
3. Мы проверяем соседние ячейки (вверх, вправо, вниз, влево) и продолжаем поиск, если находим следующую букву слова.
4. Если мы дошли до конца слова, значит, слово найдено.
5. Если все пути исследованы и слово не найдено, мы возвращаем false.

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

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Рекурсивный DFS с бэктрекингом - наиболее интуитивный и эффективный подход
   • 📝 Модификация исходной доски для отслеживания посещенных ячеек экономит память
   • 🧮 Предварительные проверки могут значительно ускорить алгоритм

2. Важные моменты:

   • 📝 Правильная обработка границ сетки
   • 🔄 Корректное отслеживание посещенных ячеек
   • 📊 Эффективное использование бэктрекинга для отмены ходов

Распространённые ошибки

1. 🤦‍♂️ Забывание восстановить исходное состояние ячейки после бэктрекинга
2. 😅 Неправильная проверка границ сетки
3. 🐛 Использование одной и той же ячейки дважды для одного слова
4. 😕 Неэффективная реализация проверки посещенных ячеек

Визуализация алгоритма

Рассмотрим пример поиска слова "CAT" в сетке:

[
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
]

1. Начинаем с первой буквы "C":

   • Находим "C" в позиции (0, 2)
   • Помечаем ячейку как посещенную
   • Ищем "A" в соседних ячейках

2. Находим "A" в позиции (1, 2):

   • Помечаем ячейку как посещенную
   • Ищем "T" в соседних ячейках

3. Не находим "T" рядом с (1, 2):

   • Отменяем ход (бэктрекинг), возвращаем исходное значение ячейки (1, 2)
   • Ищем "A" в других соседних ячейках от (0, 2)

4. Находим "A" в позиции (2, 1):

   • Помечаем ячейку как посещенную
   • Ищем "T" в соседних ячейках

5. Не находим "T" рядом с (2, 1):

   • Отменяем ход, возвращаем исходное значение ячейки (2, 1)
   • Продолжаем поиск "A" от (0, 2)

6. Пробуем другие пути, не находим "CAT" начиная с (0, 2)

7. Пробуем начать с другой буквы "C" в позиции (2, 1):

   • Помечаем ячейку как посещенную
   • Ищем "A" в соседних ячейках

8. Находим "A" в позиции (2, 2):

   • Помечаем ячейку как посещенную
   • Ищем "T" в соседних ячейках

9. Находим "T" в позиции (1, 3):

   • Помечаем ячейку как посещенную
   • Дошли до конца слова, возвращаем true

Оптимизации

Ранняя проверка размеров доски и слова

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  
  // Если слово длиннее, чем количество ячеек в доске, оно не может быть составлено
  if (word.length > rows * cols) {
    return false;
  }
  
  // Если доска состоит из одной ячейки, просто сравниваем содержимое
  if (rows === 1 && cols === 1) {
    return board[0][0] === word;
  }
  
  // Основной алгоритм
  // ...
}

Оптимизация направления поиска

function exist(board, word) {
  // ...
  
  function dfs(r, c, index) {
    // ...
    
    // Оптимизация: сначала проверяем направления, где больше вероятность найти нужную букву
    // Например, если мы ищем в начале доски, сначала идем вправо и вниз
    if (r < rows / 2 && c < cols / 2) {
      return dfs(r, c + 1, index + 1) || 
             dfs(r + 1, c, index + 1) || 
             dfs(r - 1, c, index + 1) || 
             dfs(r, c - 1, index + 1);
    } 
    // Если мы в нижней правой части, сначала идем влево и вверх
    else {
      return dfs(r - 1, c, index + 1) || 
             dfs(r, c - 1, index + 1) || 
             dfs(r + 1, c, index + 1) || 
             dfs(r, c + 1, index + 1);
    }
    
    // ...
  }
  
  // ...
}

Использование битовой маски для компактного хранения посещенных ячеек

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  
  // Для небольших досок (до 8x8) можно использовать 64-битное число
  // для отслеживания посещенных ячеек
  function dfs(r, c, index, visited) {
    if (index === word.length) {
      return true;
    }
    
    if (
      r < 0 || r >= rows || 
      c < 0 || c >= cols || 
      board[r][c] !== word[index]
    ) {
      return false;
    }
    
    // Вычисляем позицию в битовой маске
    const pos = r * cols + c;
    
    // Проверяем, посещена ли ячейка
    if (visited & (1n << BigInt(pos))) {
      return false;
    }
    
    // Устанавливаем бит в маске
    const newVisited = visited | (1n << BigInt(pos));
    
    // Проверяем четыре направления
    return dfs(r + 1, c, index + 1, newVisited) || 
           dfs(r, c + 1, index + 1, newVisited) || 
           dfs(r - 1, c, index + 1, newVisited) || 
           dfs(r, c - 1, index + 1, newVisited);
  }
  
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === word[0]) {
        if (dfs(r, c, 0, 0n)) {
          return true;
        }
      }
    }
  }
  
  return false;
}

Заключение

При решении задачи "Поиск слова" важно помнить:

• 🤹‍♂️ Поиск в глубину (DFS) с бэктрекингом - классический подход для этой задачи
• 📊 Предварительные проверки и оптимизации могут значительно улучшить производительность
• 🧠 Правильное отслеживание посещенных ячеек критически важно для корректности алгоритма
• 🔄 Восстановление исходного состояния после бэктрекинга необходимо для исследования всех возможных путей

Эта задача демонстрирует мощь алгоритмов поиска в глубину и бэктрекинга для решения задач на графах и сетках. Она также показывает, как можно эффективно использовать различные структуры данных для отслеживания состояния и оптимизации решения. 🌟