Word Search

https://leetcode.com/problems/word-search/description/

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.

DFS should do it, below, cheers, ACC.


public class Solution
{
 public bool Exist(char[,] board, string word)
 {
  if (String.IsNullOrEmpty(word)) return true;

  for (int r = 0; r < board.GetLength(0); r++)
  {
   for (int c = 0; c < board.GetLength(1); c++)
   {
    if (board[r, c] == word[0])
    {
     Hashtable visited = new Hashtable();
     visited.Add(r * board.GetLength(1) + c, true);
     if (Exist(board, visited, r, c, 1, word)) return true;
    }
   }
  }

  return false;
 }

 private bool Exist(char[,] board,
      Hashtable visited,
      int r,
      int c,
      int index,
      string word)
 {
  if (index >= word.Length) return true;

  int[] rd = { 1, -1, 0, 0 };
  int[] cd = { 0, 0, 1, -1 };

  for (int i = 0; i < rd.Length; i++)
  {
   if (r + rd[i] >= 0 &&
    r + rd[i] < board.GetLength(0) &&
    c + cd[i] >= 0 &&
    c + cd[i] < board.GetLength(1) &&
    board[r + rd[i], c + cd[i]] == word[index] &&
    !visited.ContainsKey((r + rd[i]) * board.GetLength(1) + c + cd[i]))
   {
    visited.Add((r + rd[i]) * board.GetLength(1) + c + cd[i], true);
    if (Exist(board, visited, r + rd[i], c + cd[i], index + 1, word)) return true;
    visited.Remove((r + rd[i]) * board.GetLength(1) + c + cd[i]);
   }
  }

  return false;
 }
}

Comments

  1. Nice! Python version:

    from collections import deque

    DIRECTIONS = (-1, 0, 1, 0, -1)

    class Solution:
    def exist(self, board, word):
    visited = set()

    def explore(i, j, start):
    if start == len(word):
    return False
    if start == len(word) - 1 and board[i][j] == word[-1]:
    return True
    if board[i][j] != word[start]:
    return False
    visited.add((i, j))
    for d in range(len(DIRECTIONS) - 1):
    ni, nj = i + DIRECTIONS[d], j + DIRECTIONS[d+1]
    if not (0 <= ni < len(board) and 0 <= nj < len(board[0])) or (ni, nj) in visited:
    continue
    if explore(ni, nj, start + 1):
    return True
    visited.remove((i, j))
    return False

    for i in range(len(board)):
    for j in range(len(board[i])):
    if explore(i, j, 0):
    return True
    return False

    https://gist.github.com/ttsugriy/e5792c9debab1abeb68e8334a9392a8b

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons