Word Search
https://leetcode.com/problems/word-search/description/
DFS should do it, below, cheers, ACC.
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;
}
}
Nice! Python version:
ReplyDeletefrom 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