79. Word Search

Difficulty:
Medium
Related Topics:
Similar Questions:

Problem

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

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

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Solution 1

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
  var len1 = board.length;
  var len2 = (board[0] || []).length;
  var len3 = word.length;
  var visited = null;

  if (!len1 || !len2 || !len3) return false;

  for (var i = 0; i < len1; i++) {
    for (var j = 0; j < len2; j++) {
      visited = Array(len1).fill(0).map(_ => Array(len2));
      if (helper(board, word, i, j, 0, visited)) return true;
    }
  }

  return false;
};

var helper = function (board, word, m, n, k, visited) {
  if (k === word.length) return true;
  if (m < 0 || m >= board.length) return false;
  if (n < 0 || n >= board[m].length) return false;
  if (visited[m][n]) return false;
  if (board[m][n] !== word[k]) return false;

  var res = false;

  visited[m][n] = true;

  res = helper(board, word, m - 1, n, k + 1, visited)
        || helper(board, word, m + 1, n, k + 1, visited)
        || helper(board, word, m, n - 1, k + 1, visited)
        || helper(board, word, m, n + 1, k + 1, visited);

  if (!res) visited[m][n] = false;

  return res;
};

Explain:

nope.

Complexity:

Solution 2

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
  var len1 = board.length;
  var len2 = (board[0] || []).length;
  var len3 = word.length;

  if (!len1 || !len2 || !len3) return false;

  for (var i = 0; i < len1; i++) {
    for (var j = 0; j < len2; j++) {
      if (helper(board, word, i, j, 0)) return true;
    }
  }

  return false;
};

var helper = function (board, word, m, n, k) {
  if (k === word.length) return true;
  if (m < 0 || m >= board.length) return false;
  if (n < 0 || n >= board[m].length) return false;
  if (board[m][n] !== word[k]) return false;

  var res = false;
  var char = board[m][n];

  board[m][n] = '#';

  res = helper(board, word, m - 1, n, k + 1)
        || helper(board, word, m + 1, n, k + 1)
        || helper(board, word, m, n - 1, k + 1)
        || helper(board, word, m, n + 1, k + 1);

  if (!res) board[m][n] = char;

  return res;
};

Explain:

上一方法的优化，用过的字符不再用 visited 数组存储，直接修改用过的字符为 #。

Complexity: