79. Word Search I & II

Reference: Problem I & Problem II
Difficulty: Medium

Problem I

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.

board = [['A']]
Given word = "A", return true.

board = [] or word = null
return false.

Follow up: Reduce space complexity to $O(1)$.

Analysis

Backtracking

Consider how to write accept and reject base cases.

public boolean exist(char[][] board, String word) {
  if (word == null || word.length() == 0 || board == null || board.length == 0) {
    return false;
  }
  int m = board.length;
  int n = board[0].length;
  boolean[][] visit = new boolean[m][n]; // since each cell is visited once
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if (backtracking(0, i, j, board, word, visit)) return true;
    }
  }
  return false;
}

int[][] direction = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

private boolean backtracking(int pos, int i, int j, char[][] board, String word, boolean[][] visit) {
  // reject - character not equal
  if (pos == word.length() || word.charAt(pos) != board[i][j]) {
    return false;
  }
  // accept
  if (pos == word.length() - 1) {
    return true;
  }
  // visit
  visit[i][j] = true;
  // check its neighbors
  int m = board.length;
  int n = board[0].length;
  for (int[] dir : direction) {
    int x = i + dir[0];
    int y = j + dir[1];
    if (x >= 0 && x < m && y >= 0 && y < n && !visit[x][y]) {
      if (backtracking(pos + 1, x, y, board, word, visit)) {
        return true;
      }
    }
  }
  visit[i][j] = false;
  return false;
}

Can be optimized by setting board[i][j] ^= 256 and check if board[x][y] is less than 256. So we don’t need extra space.

Time: $O(MN \times 4^K)$ where $K$ is the length of the string.
Space: $O(MN)$

Problem II

Marked

Use Trie.

https://leetcode.com/problems/word-search-ii/discuss/59780/Java-15ms-Easiest-Solution-(100.00)