Given a 2D board of letters and a word. Check if the word exists in the board. The word can be constructed from letters of adjacent cells only. ie - horizontal or vertical neighbors. The same letter cell can not be used more than once.
Example 1:
Input: board = {{a,g,b,c},{q,e,e,l},{g,b,k,s}},
word = "geeks"
Output: 1
Explanation: The board is-
a g b c
q e e l
g b k s
The letters which are used to make the
"geeks" are colored.
Example 2:
Input: board = {{a,b,c,e},{s,f,c,s},{a,d,e,e}},
word = "sabfs"
Output: 0
Explanation: The board is-
a b c e
s f c s
a d e e
Same letter can not be used twice hence ans is 0
Your Task:
You don't need to read or print anything. Your task is to complete the function isWordExist() which takes board and word as input parameter and returns boolean value true if word can be found otherwise returns false.
Expected Time Complexity: O(N * M * 4^{L}) where N = No. of rows in board, M = No. of columns in board, L = Length of word
Expected Space Compelxity: O(L), L is length of word.
Constraints:
1 ≤ N, M ≤ 100
1 ≤ L ≤ N*M

Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(N * M * 4^{L}) where N = No. of rows in board, M = No. of columns in board, L = Length of word
Expected Auxiliary Space: O(L), L is length of word.

Starter code:
class Solution:

	def isWordExist(self, board, word):

		#Code here

Solutions:
class Solution:

	def explore(self, board, word, i, j, idx):
		n = len(board)
		m = len(board[0])
		if idx == len(word):
			return True
		if i < 0 or i >= n or j < 0 or (j >= m) or (board[i][j] == '.') or (board[i][j] != word[idx]):
			return False
		temp_c = board[i][j]
		board[i][j] = '.'
		top = self.explore(board, word, i - 1, j, idx + 1)
		bottom = self.explore(board, word, i + 1, j, idx + 1)
		left = self.explore(board, word, i, j - 1, idx + 1)
		right = self.explore(board, word, i, j + 1, idx + 1)
		board[i][j] = temp_c
		return top or bottom or left or right

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		idx = 0
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[idx]:
					if self.explore(board, word, i, j, idx):
						return 1
		return 0


from itertools import product
from collections import Counter

class Solution:

	def isWordExist(self, board, word):
		(m, n) = (len(board), len(board[0]))
		b = Counter((board[i][j] for (i, j) in product(range(m), range(n))))
		w = Counter(word)
		if len(w) > len(b):
			return 0

		def dfs(r, c, index):
			if index == len(word):
				return 1
			if r < 0 or r == m or c < 0 or (c == n) or (board[r][c] != word[index]):
				return 0
			board[r][c] = '@'
			if dfs(r + 1, c, index + 1):
				return 1
			if dfs(r - 1, c, index + 1):
				return 1
			if dfs(r, c + 1, index + 1):
				return 1
			if dfs(r, c - 1, index + 1):
				return 1
			board[r][c] = word[index]
		for (i, j) in product(range(m), range(n)):
			if dfs(i, j, 0):
				return 1
		return 0


from collections import defaultdict

class Solution:

	def isWordExist(self, board, word):
		d1 = defaultdict(int)
		for i in word:
			d1[i] += 1
		dire = [(-1, 0), (0, -1), (1, 0), (0, 1)]

		def dfs(r, c, d, vis, ind):
			if r >= len(board) or r < 0 or c >= len(board[0]) or (c < 0) or ((r, c) in vis) or (ind >= len(word)):
				return False
			vis.add((r, c))
			s = board[r][c]
			if s == word[ind]:
				d[s] += 1
				for i in dire:
					(x, y) = (r + i[0], c + i[1])
					dfs(x, y, d, vis, ind + 1)
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					vis = set()
					d = defaultdict(int)
					dfs(i, j, d, vis, 0)
					flag = True
					for (key, val) in d1.items():
						if key in d:
							if val > d[key]:
								flag = False
								break
						else:
							flag = False
							break
					if flag:
						return True
		return False


class Solution:

	def search(self, board, word, index, board_i, board_j):
		if index == len(word):
			return True
		if board_i < 0 or board_i == len(board) or board_j < 0 or (board_j == len(board[0])):
			return False
		if board[board_i][board_j] != word[index]:
			return False
		board[board_i][board_j] = '!'
		for (movi, movj) in self.directions:
			found = self.search(board, word, index + 1, board_i + movi, board_j + movj)
			if found:
				return True
		board[board_i][board_j] = word[index]
		return False

	def isWordExist(self, board, word):
		self.directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		for i in range(len(board)):
			for j in range(len(board[0])):
				found = self.search(board, word, 0, i, j)
				if found:
					return True
		return False


class Solution:

	def __init__(self):
		self.ans = False

	def solve(self, word, pos, board, i, j, n, m, vis, ind):
		if pos == ind - 1:
			self.ans = True
			return
		vis[i][j] = True
		for (x1, y1) in self.next:
			(x, y) = (i + x1, j + y1)
			if -1 < x < n and -1 < y < m and (word[pos + 1] == board[x][y]) and (vis[x][y] == False):
				self.solve(word, pos + 1, board, x, y, n, m, vis, ind)
		vis[i][j] = False

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		self.next = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		vis = [[False for _ in range(m)] for _ in range(n)]
		for i in range(n):
			for j in range(m):
				if word[0] == board[i][j]:
					self.solve(word, 0, board, i, j, n, m, vis, len(word))
			if self.ans == True:
				return True
		return self.ans


class Solution:

	def helper(self, board, x, y, row, col, word, pos, len1):
		if pos == len1 - 1:
			self.res = 1
			return
		(temp, board[x][y]) = (board[x][y], -1)
		for (x1, y1) in self.next:
			(x2, y2) = (x + x1, y + y1)
			if -1 < x2 < row and -1 < y2 < col and (board[x2][y2] == word[pos + 1]):
				self.helper(board, x2, y2, row, col, word, pos + 1, len1)
		board[x][y] = temp

	def isWordExist(self, board, word):
		(row, col) = (len(board), len(board[0]))
		self.next = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		self.res = 0
		for i in range(row):
			for j in range(col):
				if board[i][j] == word[0]:
					self.helper(board, i, j, row, col, word, 0, len(word))
					if self.res:
						return 1
		return 0


class Solution:

	def isWordExist(self, board, word):
		rows = len(board)
		cols = len(board[0])
		path = set()

		def dfs(r, c, i):
			if i == len(word):
				return True
			if r < 0 or c < 0 or r >= rows or (c >= cols) or (word[i] != board[r][c]) or ((r, c) in path):
				return False
			path.add((r, c))
			res = dfs(r + 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c - 1, i + 1)
			path.remove((r, c))
			return res
		for r in range(rows):
			for c in range(cols):
				if dfs(r, c, 0):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		rows = len(board)
		col = len(board[0])
		index = 0
		for i in range(0, rows):
			for j in range(0, col):
				if board[i][j] == word[index]:
					if self.getAns(i, j, index, rows, col, board, word):
						return True
		return False

	def getAns(self, i, j, ind, m, n, board, word):
		if ind == len(word):
			return True
		if i < 0 or j < 0 or i == m or (j == n) or (board[i][j] != word[ind]) or (board[i][j] == '!'):
			return False
		c = board[i][j]
		board[i][j] = '!'
		top = self.getAns(i - 1, j, ind + 1, m, n, board, word)
		left = self.getAns(i, j - 1, ind + 1, m, n, board, word)
		right = self.getAns(i, j + 1, ind + 1, m, n, board, word)
		bot = self.getAns(i + 1, j, ind + 1, m, n, board, word)
		board[i][j] = c
		return top or left or right or bot


class Solution:

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		path = set()

		def solve(row, col, ind):
			if ind == len(word):
				return True
			if row < 0 or col < 0 or row >= n or (col >= m) or (word[ind] != board[row][col]) or ((row, col) in path):
				return False
			path.add((row, col))
			res = solve(row + 1, col, ind + 1) or solve(row - 1, col, ind + 1) or solve(row, col + 1, ind + 1) or solve(row, col - 1, ind + 1)
			path.remove((row, col))
			return res
		for i in range(n):
			for j in range(m):
				if solve(i, j, 0):
					return True
		return False


from collections import defaultdict, Counter

class Solution:

	def isWordExist(self, board, word):
		(ROWS, COLS) = (len(board), len(board[0]))
		path = set()

		def dfs(r, c, i):
			if i == len(word):
				return True
			if min(r, c) < 0 or r >= ROWS or c >= COLS or (word[i] != board[r][c]) or ((r, c) in path):
				return False
			path.add((r, c))
			res = dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1)
			return res
		for r in range(ROWS):
			for c in range(COLS):
				if dfs(r, c, 0):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		(ROWS, COLS) = (len(board), len(board[0]))
		path = set()

		def dfs(r, c, i):
			if i == len(word):
				return True
			if min(r, c) < 0 or r >= ROWS or c >= COLS or (word[i] != board[r][c]) or ((r, c) in path):
				return False
			path.add((r, c))
			res = dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1)
			path.remove((r, c))
			return res
		for r in range(ROWS):
			for c in range(COLS):
				if dfs(r, c, 0):
					return True
		return False


class Solution:
	ans = 0

	def dfs(self, board, word, i, j, visited, ch):
		if ch == word:
			self.ans = 1
			return
		if len(ch) > len(word):
			return
		visited[i][j] = 1
		if i - 1 >= 0 and visited[i - 1][j] == 0 and (word[len(ch)] == board[i - 1][j]):
			visited[i - 1][j] = 1
			self.dfs(board, word, i - 1, j, visited, ch + board[i - 1][j])
			if self.ans:
				return
			visited[i - 1][j] = 0
		if j - 1 >= 0 and visited[i][j - 1] == 0 and (word[len(ch)] == board[i][j - 1]):
			visited[i][j - 1] = 1
			self.dfs(board, word, i, j - 1, visited, ch + board[i][j - 1])
			if self.ans:
				return
			visited[i][j - 1] = 0
		if j + 1 < len(board[0]) and visited[i][j + 1] == 0 and (word[len(ch)] == board[i][j + 1]):
			visited[i][j + 1] = 1
			self.dfs(board, word, i, j + 1, visited, ch + board[i][j + 1])
			if self.ans:
				return
			visited[i][j + 1] = 0
		if i + 1 < len(board) and visited[i + 1][j] == 0 and (word[len(ch)] == board[i + 1][j]):
			visited[i + 1][j] = 1
			self.dfs(board, word, i + 1, j, visited, ch + board[i + 1][j])
			if self.ans:
				return
			visited[i + 1][j] = 0
		visited[i][j] = 0

	def isWordExist(self, board, word):
		self.ans = 0
		visited = []
		for i in range(len(board) + 1):
			arr = []
			for j in range(len(board[0]) + 1):
				arr.append(0)
			visited.append(arr)
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					self.dfs(board, word, i, j, visited, board[i][j])
					if self.ans:
						return 1
		return 0


from collections import deque

class Solution:

	def isWordExist(self, board, word):
		dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]
		(n, m) = (len(board), len(board[0]))
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					q = deque()
					q.append([i, j])
					vis = [[0] * m for i in range(n)]
					vis[i][j] = 1
					ind = 1
					while len(q) != 0:
						(row, col) = q.popleft()
						if ind == len(word):
							return True
						for (trow, tcol) in dir:
							trow += row
							tcol += col
							if trow < 0 or tcol < 0 or trow >= n or (tcol >= m) or vis[trow][tcol] or (board[trow][tcol] != word[ind]):
								continue
							else:
								q.append([trow, tcol])
								vis[trow][tcol] = 1
								ind += 1
							if ind == len(word):
								return True
		return False


class Solution:

	def helper(self, r, c, rows, cols, board, word):
		positionList = [(0, -1), (0, 1), (-1, 0), (1, 0)]
		if len(word) == 0:
			self.result = 1
			return
		temp = board[r][c]
		board[r][c] = -1
		for pos in positionList:
			r = r + pos[0]
			c = c + pos[1]
			if 0 <= r < rows and 0 <= c < cols and (board[r][c] == word[0]):
				self.helper(r, c, rows, cols, board, word[1:])
			r -= pos[0]
			c -= pos[1]
		board[r][c] = temp

	def isWordExist(self, board, word):
		self.result = 0
		index_of_word = 0
		rows = len(board)
		cols = len(board[0])
		for i in range(rows):
			for j in range(cols):
				if board[i][j] == word[0]:
					self.helper(i, j, rows, cols, board, word[1:])
					if self.result == 1:
						return True
		return False


class Solution:

	def isWordExist(self, board, word):

		def calc(r, c, pos):
			if pos == len(word):
				return True
			for (nr, nc) in [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]:
				if nr >= 0 and nr < len(board) and (nc >= 0) and (nc < len(board[0])) and (board[nr][nc] == word[pos]) and (vis[nr][nc] == 0):
					vis[nr][nc] = 1
					if calc(nr, nc, pos + 1):
						return True
					vis[nr][nc] = 0
			return False
		vis = [[0 for i in range(len(board[0]))] for j in range(len(board))]
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					vis[i][j] = 1
					if calc(i, j, 1):
						return True
					vis[i][j] = 0
		return False


class Solution:

	def isWordExist(self, board, word):
		rows = len(board)
		cols = len(board[0])
		if len(word) > rows * cols:
			return False

		def dfs(i, j, index):
			if index == len(word):
				return True
			if i < 0 or i >= rows or j < 0 or (j >= cols) or (board[i][j] != word[index]):
				return False
			board[i][j] = '#'
			found = dfs(i - 1, j, index + 1) or dfs(i + 1, j, index + 1) or dfs(i, j - 1, index + 1) or dfs(i, j + 1, index + 1)
			board[i][j] = word[index]
			return found
		for i in range(rows):
			for j in range(cols):
				if dfs(i, j, 0):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		visited = set()
		(ROW, COL, N) = (len(board), len(board[0]), len(word))
		for i in range(ROW):
			for j in range(COL):
				if self.helper(i, j, ROW, COL, 0, board, word, N, visited):
					return True
		return False

	def helper(self, i, j, row, column, index, board, word, N, visited):
		if index == N:
			return True
		if not 0 <= i < row or not 0 <= j < column or (not board[i][j] == word[index]) or ((i, j) in visited):
			return False
		visited.add((i, j))
		possible = self.helper(i + 1, j, row, column, index + 1, board, word, N, visited) or self.helper(i - 1, j, row, column, index + 1, board, word, N, visited) or self.helper(i, j + 1, row, column, index + 1, board, word, N, visited) or self.helper(i, j - 1, row, column, index + 1, board, word, N, visited)
		visited.remove((i, j))
		return possible


class Solution:

	def isWordExist(self, board, word):

		def funcall(row, col, rows, cols, temp):
			if temp == word:
				return True
			if row < 0 or row >= rows or col < 0 or (col >= cols) or (board[row][col] == -1) or (len(temp) > len(word)) or (temp != word[:len(temp)]):
				return False
			vari = board[row][col]
			board[row][col] = -1
			if funcall(row + 1, col, rows, cols, temp + vari):
				board[row][col] = vari
				return True
			if funcall(row - 1, col, rows, cols, temp + vari):
				board[row][col] = vari
				return True
			if funcall(row, col + 1, rows, cols, temp + vari):
				board[row][col] = vari
				return True
			if funcall(row, col - 1, rows, cols, temp + vari):
				board[row][col] = vari
				return True
			board[row][col] = vari
			return False
		rows = len(board)
		cols = len(board[0])
		temp = ''
		for i in range(rows):
			for j in range(cols):
				ans = funcall(i, j, rows, cols, temp)
				if ans:
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		m = len(board)
		n = len(board[0])
		ind = 0
		for i in range(m):
			for j in range(n):
				if board[i][j] == word[ind]:
					if self.search(board, word, i, j, ind, m, n):
						return True
		return False

	def search(self, board, word, row, col, ind, m, n):
		if ind == len(word):
			return True
		if row < 0 or col < 0 or row == m or (col == n) or (board[row][col] != word[ind]) or (board[row][col] == '!'):
			return False
		c = board[row][col]
		board[row][col] = '!'
		top = self.search(board, word, row - 1, col, ind + 1, m, n)
		left = self.search(board, word, row, col - 1, ind + 1, m, n)
		right = self.search(board, word, row, col + 1, ind + 1, m, n)
		down = self.search(board, word, row + 1, col, ind + 1, m, n)
		board[row][col] = c
		return top or left or right or down


class Solution:

	def isWordExist(self, board, word):
		val = False

		def recurs(i, j, target, curr):
			nonlocal val
			if i >= len(board) or i < 0 or j >= len(board[0]) or (j < 0) or ((i, j) in curr):
				if target >= len(word):
					val = True
				return False
			if target >= len(word):
				val = True
				return
			if board[i][j] == word[target]:
				curr.append((i, j))
				recurs(i + 1, j, target + 1, curr)
				recurs(i - 1, j, target + 1, curr)
				recurs(i, j + 1, target + 1, curr)
				recurs(i, j - 1, target + 1, curr)
				curr.pop()
			return
		for i in range(len(board)):
			for j in range(len(board[0])):
				if val == True:
					return True
				if board[i][j] == word[0]:
					curr = []
					recurs(i, j, 0, curr)
		if val:
			return True
		return False


class Solution:

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		seen = [[False for i in range(m)] for j in range(n)]
		dx = [1, 0, -1, 0]
		dy = [0, 1, 0, -1]

		def dfs(i, j, k):
			if k == len(word):
				return True
			for t in range(4):
				r = i + dx[t]
				c = j + dy[t]
				if 0 <= r < n and 0 <= c < m and (board[r][c] == word[k]) and (not seen[r][c]):
					seen[r][c] = True
					if dfs(r, c, k + 1):
						return True
					seen[r][c] = False
			return False
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0] and (not seen[i][j]):
					seen[i][j] = True
					if dfs(i, j, 1):
						return True
					seen[i][j] = False
		return False


class Solution:

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		uni = set()

		def search(x, y, ind):
			if ind == len(word):
				return True
			if x < 0 or y < 0 or x >= n or (y >= m):
				return False
			elif word[ind] != board[x][y]:
				return False
			elif (x, y) in uni:
				return False
			uni.add((x, y))
			res = search(x + 1, y, ind + 1) or search(x - 1, y, ind + 1) or search(x, y + 1, ind + 1) or search(x, y - 1, ind + 1)
			uni.remove((x, y))
			return res
		for i in range(n):
			for j in range(m):
				if search(i, j, 0):
					return True
		return False


class Solution:

	def __init__(self):
		self.flag = False

	def dfs(self, board, i, j, n, m, curr_word, word):
		if self.flag:
			return
		if curr_word >= len(word):
			self.flag = True
			return True
		if i < 0 or i >= n or j < 0 or (j >= m) or (board[i][j] == '#') or (board[i][j] != word[curr_word]):
			return
		ch = board[i][j]
		board[i][j] = '#'
		self.dfs(board, i + 1, j, n, m, curr_word + 1, word)
		self.dfs(board, i, j + 1, n, m, curr_word + 1, word)
		self.dfs(board, i - 1, j, n, m, curr_word + 1, word)
		self.dfs(board, i, j - 1, n, m, curr_word + 1, word)
		board[i][j] = ch

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:
					self.dfs(board, i, j, n, m, 0, word)
					if self.flag:
						return True
		return False


class Solution:

	def isWordExist(self, board, word):

		def findword(board, word, visited, row, col, arr):
			visited[row][col] = True
			if len(word) == 0:
				return True
			for i in arr:
				if row + i[0] >= 0 and row + i[0] < len(board) and (col + i[1] >= 0) and (col + i[1] < len(board[0])) and (visited[row + i[0]][col + i[1]] == False) and (board[row + i[0]][col + i[1]] == word[0]):
					if findword(board, word[1:], visited, row + i[0], col + i[1], arr):
						return True
					else:
						visited[row + i[0]][col + i[1]] = False
		visited = [[False for i in range(len(board[0]))] for j in range(len(board))]
		arr = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					if findword(board, word[1:], visited, i, j, arr):
						return True
					else:
						visited[i][j] = False
		return False


class Solution:

	def isWordExist(self, board, word):

		def find(i, j, pos, board):
			if pos >= len(word):
				return True
			if i < 0 or j < 0 or i >= len(board) or (j >= len(board[0])):
				return False
			if board[i][j] != word[pos]:
				return False
			temp = board[i][j]
			board[i][j] = '$'
			top = find(i - 1, j, pos + 1, board)
			left = find(i, j - 1, pos + 1, board)
			bottom = find(i + 1, j, pos + 1, board)
			right = find(i, j + 1, pos + 1, board)
			board[i][j] = temp
			return top or left or right or bottom
		for i in range(len(board)):
			for j in range(len(board[i])):
				if find(i, j, 0, board):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		(n, m) = (len(board), len(board[0]))
		seen = set()

		def helper(i, j, idx):
			if idx == len(word):
				return True
			if (i >= n or j >= m or i < 0 or (j < 0)) or (i, j) in seen or board[i][j] != word[idx]:
				return False
			seen.add((i, j))
			res = helper(i + 1, j, idx + 1) or helper(i - 1, j, idx + 1) or helper(i, j - 1, idx + 1) or helper(i, j + 1, idx + 1)
			seen.remove((i, j))
			return res
		for i in range(n):
			for j in range(m):
				if helper(i, j, 0):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):

		def dfs(board, i, j, word):
			if not word:
				return True
			if i < 0 or j < 0 or i == len(board) or (j == len(board[0])) or (board[i][j] != word[0]):
				return False
			tmp = board[i][j]
			board[i][j] = '#'
			res = dfs(board, i + 1, j, word[1:]) or dfs(board, i - 1, j, word[1:]) or dfs(board, i, j + 1, word[1:]) or dfs(board, i, j - 1, word[1:])
			board[i][j] = tmp
			return res
		for i in range(len(board)):
			for j in range(len(board[0])):
				if dfs(board, i, j, word):
					return True
		return False


def isExist(board, r, c, p, q, word, i, n, visit):
	if i == n:
		return True
	if r < 0 or r >= p or c < 0 or (c >= q) or visit[r][c] or (board[r][c] != word[i]):
		return False
	dr = [0, 0, 1, -1]
	dc = [1, -1, 0, 0]
	visit[r][c] = True
	for k in range(4):
		(r_, c_) = (r + dr[k], c + dc[k])
		if isExist(board, r_, c_, p, q, word, i + 1, n, visit):
			return True
	visit[r][c] = False
	return False

class Solution:

	def isWordExist(self, board, word):
		(p, q) = (len(board), len(board[0]))
		n = len(word)
		visit = [[False for c in range(q)] for r in range(p)]
		for r in range(p):
			for c in range(q):
				if isExist(board, r, c, p, q, word, 0, n, visit):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		l = len(word)
		n = len(board)
		m = len(board[0])
		dic = {}
		mat = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:
					dic[str(i) + str(j)] = 1
					ans = self.recurse(board, i, j, 1, dic, l, mat, n, m)
					if ans:
						return True
					else:
						dic.pop(str(i) + str(j))
		return False

	def recurse(self, board, row, col, w, dic, l, mat, n, m):
		if w >= l:
			return True
		for el in mat:
			(x, y) = (row + el[0], col + el[1])
			s = str(x) + str(y)
			if x >= 0 and x < n and (y >= 0) and (y < m) and (board[x][y] == word[w]) and (s not in dic):
				dic[s] = 1
				ans = self.recurse(board, x, y, w + 1, dic, l, mat, n, m)
				if ans:
					return True
				else:
					dic.pop(s)
		return False


class Solution:

	def helper(self, board, word, i, j, n, m, k):
		if k > len(word) - 1:
			return True
		if i < 0 or i >= n or j < 0 or (j >= m) or (board[i][j] == '.') or (word[k] != board[i][j]):
			return False
		board[i][j] = '.'
		x = [0, 0, -1, 1]
		y = [-1, 1, 0, 0]
		temp = False
		for ind in range(4):
			temp = temp or self.helper(board, word, i + x[ind], j + y[ind], n, m, k + 1)
		board[i][j] = word[k]
		return temp

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		for i in range(len(board)):
			for j in range(len(board[0])):
				if self.helper(board, word, i, j, n, m, 0):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		starts = []
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:
					starts.append((i, j))
		output = []
		for (x, y) in starts:
			output += self.helper(word, 1, x, y, n, m, board, set())
		return int(any(output))

	def helper(self, word, i, x, y, n, m, board, path):
		if (x, y) in path:
			return [False]
		path.add((x, y))
		if i == len(word):
			return [True]
		output = [False]
		if x > 0 and board[x - 1][y] == word[i]:
			output += self.helper(word, i + 1, x - 1, y, n, m, board, path.copy())
		if x < n - 1 and board[x + 1][y] == word[i]:
			output += self.helper(word, i + 1, x + 1, y, n, m, board, path.copy())
		if y > 0 and board[x][y - 1] == word[i]:
			output += self.helper(word, i + 1, x, y - 1, n, m, board, path.copy())
		if y < m - 1 and board[x][y + 1] == word[i]:
			output += self.helper(word, i + 1, x, y + 1, n, m, board, path.copy())
		return [any(output)]


def func(pos, board, word, visted, ans, index):
	(i, j) = pos
	if 0 <= i < len(board) and 0 <= j < len(board[0]) and (board[i][j] == word[index]) and ((i, j) not in visted) and (index < len(word)):
		visted.add((i, j))
		if index == len(word) - 1:
			ans[0] = True
			return
		func((i + 1, j), board, word, visted, ans, index + 1)
		func((i, j + 1), board, word, visted, ans, index + 1)
		func((i - 1, j), board, word, visted, ans, index + 1)
		func((i, j - 1), board, word, visted, ans, index + 1)
		visted.remove((i, j))

class Solution:

	def isWordExist(self, board, word):
		ans = [False]
		for i in range(len(board)):
			for j in range(len(board[0])):
				visted = set()
				if board[i][j] == word[0]:
					func((i, j), board, word, visted, ans, 0)
					if ans[0]:
						return True
		return False


class Solution:

	def isWordExist(self, board, word):
		(n, m) = (len(board), len(board[0]))
		x = set()

		def dfs(i, j, n, m, ind, s):
			if i < 0 or j < 0 or i >= n or (j >= m) or ((i, j) in v):
				return
			if s[ind] != board[i][j]:
				return False
			if len(s) - 1 == ind:
				return True
			v.add((i, j))
			a = dfs(i + 1, j, n, m, ind + 1, s)
			b = dfs(i - 1, j, n, m, ind + 1, s)
			c = dfs(i, j + 1, n, m, ind + 1, s)
			d = dfs(i, j - 1, n, m, ind + 1, s)
			return a or b or c or d
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:
					v = set()
					if dfs(i, j, n, m, 0, word):
						return True
		return False


class Solution:

	def isWordExist(self, board, word):

		def dfs(x, y, i):
			if i == len(word):
				return True
			if x < 0 or y < 0 or x == len(board) or (y == len(board[0])) or (board[x][y] != word[i]):
				return False
			board[x][y] = '_'
			for k in range(-1, 2, 2):
				if dfs(x + k, y, i + 1) or dfs(x, y + k, i + 1):
					return True
			board[x][y] = word[i]
			return False
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0] and dfs(i, j, 0):
					return True
		return False


from collections import defaultdict
from collections import Counter

class Solution:

	def isWordExist(self, board, word):
		boardDic = defaultdict(int)
		for i in range(len(board)):
			for j in range(len(board[0])):
				boardDic[board[i][j]] += 1
		wordDic = Counter(word)
		for c in wordDic:
			if c not in boardDic or boardDic[c] < wordDic[c]:
				return False
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					if self.dfs(i, j, 0, board, word):
						return True
		return False

	def dfs(self, i, j, k, board, word):
		if i < 0 or j < 0 or i >= len(board) or (j >= len(board[0])) or (k >= len(word)) or (word[k] != board[i][j]):
			return False
		if k == len(word) - 1:
			return True
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		for (x, y) in directions:
			tmp = board[i][j]
			board[i][j] = -1
			if self.dfs(i + x, j + y, k + 1, board, word):
				return True
			board[i][j] = tmp


class Solution:

	def isWordExist(self, board, word):

		def search(i, j, m, n, board, word, k):
			if k == len(word):
				return True
			if i < 0 or j < 0 or i == m or (j == n) or (board[i][j] != word[k]):
				return False
			c = board[i][j]
			board[i][j] = '#'
			op1 = search(i + 1, j, m, n, board, word, k + 1)
			op2 = search(i, j + 1, m, n, board, word, k + 1)
			op3 = search(i - 1, j, m, n, board, word, k + 1)
			op4 = search(i, j - 1, m, n, board, word, k + 1)
			board[i][j] = c
			return op1 or op2 or op3 or op4
		m = len(board)
		n = len(board[0])
		for i in range(m):
			for j in range(n):
				if board[i][j] == word[0]:
					if search(i, j, m, n, board, word, 0):
						return True
		return False


poss = [[0, 1], [0, -1], [1, 0], [-1, 0]]

class Solution:

	def isWordExist(self, board, word):
		visited = [[False for j in range(len(board[0]))] for i in range(len(board))]
		for i in range(len(board)):
			for j in range(len(board[0])):
				if self.dfs(i, j, board, visited, word, 0):
					return 1
		return 0

	def dfs(self, i, j, board, visited, word, ind):
		if ind == len(word):
			return True
		if not (i >= 0 and i < len(board) and (j >= 0) and (j < len(board[0]))) or visited[i][j] or board[i][j] != word[ind]:
			return False
		visited[i][j] = True
		for (a, b) in poss:
			if self.dfs(i + a, j + b, board, visited, word, ind + 1):
				return True
		visited[i][j] = False
		return False


from itertools import product
from collections import Counter

class Solution:

	def isWordExist(self, B, W):
		(m, n) = (len(B), len(B[0]))

		def dfs(r, c, index):
			if index == len(W):
				return 1
			if r < 0 or r == m or c < 0 or (c == n) or (B[r][c] != W[index]):
				return 0
			B[r][c] = '@'
			if dfs(r + 1, c, index + 1):
				return 1
			elif dfs(r - 1, c, index + 1):
				return 1
			elif dfs(r, c + 1, index + 1):
				return 1
			elif dfs(r, c - 1, index + 1):
				return 1
			B[r][c] = W[index]
		for (i, j) in product(range(m), range(n)):
			if dfs(i, j, 0):
				return 1
		return 0


class Solution:

	def isWordExist(self, board, word):
		m = len(board)
		n = len(board[0])
		N = len(word)

		def dfs(i, j, pos, vis):
			if i < 0 or j < 0 or i >= m or (j >= n) or (vis[i][j] == True) or (board[i][j] != word[pos]):
				return 0
			if pos == N - 1:
				return True
			vis[i][j] = True
			ans = dfs(i + 1, j, pos + 1, vis) + dfs(i, j + 1, pos + 1, vis) + dfs(i, j - 1, pos + 1, vis) + dfs(i - 1, j, pos + 1, vis)
			vis[i][j] = False
			return ans
		for i in range(m):
			for j in range(n):
				if board[i][j] == word[0]:
					vis = [[False for _ in range(n)] for _ in range(m)]
					if dfs(i, j, 0, vis):
						return 1
		return 0


class Solution:

	def isWordExist(self, board, word):
		for i in range(0, len(board)):
			for j in range(0, len(board[0])):
				visited = []
				for k in range(0, len(board)):
					visited.append([0] * len(board[0]))
				start = 0
				if board[i][j] == word[start]:
					flag = self.find(i, j, start + 1, board, word, visited)
					if flag == 1:
						return 1
		return 0

	def find(self, i, j, start, board, word, visited):
		visited[i][j] = 1
		if start == len(word):
			return 1
		if start > len(word):
			return 0
		if i - 1 >= 0:
			if board[i - 1][j] == word[start]:
				if visited[i - 1][j] != 1:
					flag = self.find(i - 1, j, start + 1, board, word, visited)
					if flag == 1:
						return 1
			if j - 1 >= 0:
				if board[i][j - 1] == word[start]:
					if visited[i][j - 1] != 1:
						flag = self.find(i, j - 1, start + 1, board, word, visited)
						if flag == 1:
							return 1
			if j + 1 < len(board[0]):
				if board[i][j + 1] == word[start]:
					if visited[i][j + 1] != 1:
						flag = self.find(i, j + 1, start + 1, board, word, visited)
						if flag == 1:
							return 1
		if j - 1 >= 0:
			if board[i][j - 1] == word[start]:
				if visited[i][j - 1] != 1:
					flag = self.find(i, j - 1, start + 1, board, word, visited)
					if flag == 1:
						return 1
		if j + 1 < len(board[0]):
			if board[i][j + 1] == word[start]:
				if visited[i][j + 1] != 1:
					flag = self.find(i, j + 1, start + 1, board, word, visited)
					if flag == 1:
						return 1
		if i + 1 < len(board):
			if board[i + 1][j] == word[start]:
				if visited[i + 1][j] != 1:
					flag = self.find(i + 1, j, start + 1, board, word, visited)
					if flag == 1:
						return 1
		return 0


class Solution:

	def isWordExist(self, M, w):
		(R, C) = (len(M), len(M[0]))
		for r in range(R):
			for c in range(C):
				if M[r][c] == w[0] and dfs(r, c, w, 0, set(), M, R, C):
					return True
		return False

def dfs(r, c, w, i, v, M, R, C):
	if i == len(w):
		return True
	if r < 0 or r == R or c < 0 or (c == C):
		return False
	if M[r][c] != w[i]:
		return False
	if (r, c) in v:
		return False
	v.add((r, c))
	for (nr, nc) in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
		if dfs(nr, nc, w, i + 1, v, M, R, C):
			return True
	v.remove((r, c))
	return False


def dfs(graph, x, y, word, i, visited):
	if i >= len(word):
		return True
	if x < 0 or y < 0 or x >= len(graph) or (y >= len(graph[0])) or visited[x][y] or (graph[x][y] != word[i]):
		return False
	visited[x][y] = True
	ans = dfs(graph, x - 1, y, word, i + 1, visited) or dfs(graph, x + 1, y, word, i + 1, visited) or dfs(graph, x, y - 1, word, i + 1, visited) or dfs(graph, x, y + 1, word, i + 1, visited)
	visited[x][y] = False
	return ans

class Solution:

	def isWordExist(self, board, word):
		visited = [[0] * len(board[0]) for i in range(len(board))]
		for i in range(len(board)):
			for j in range(len(board[0])):
				if dfs(board, i, j, word, 0, visited):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		vis = set()
		m = len(board)
		n = len(board[0])

		def capture(r, c, ind):
			if r < 0 or c < 0 or r == m or (c == n) or (board[r][c] != word[ind]) or ((r, c) in vis):
				return
			if ind == len(word) - 1:
				return True
			vis.add((r, c))
			res = capture(r + 1, c, ind + 1) or capture(r - 1, c, ind + 1) or capture(r, c + 1, ind + 1) or capture(r, c - 1, ind + 1)
			vis.remove((r, c))
			return res
		for i in range(m):
			for j in range(n):
				if capture(i, j, 0):
					return True
		return False


def wordSearch(board, word):
	(n, m) = (len(board), len(board[0]))
	for i in range(n):
		for j in range(m):
			if board[i][j] == word[0]:
				vis = set()
				vis.add((i, j))
				text = board[i][j]
				ind = 1
				res = helper(i, j, n, m, board, vis, text, ind, word)
				if res:
					return True
	return False

def helper(i, j, n, m, board, vis, text, ind, word):
	if text == word:
		return True
	for (ti, tj) in zip([1, -1, 0, 0], [0, 0, 1, -1]):
		(ni, nj) = (ti + i, tj + j)
		if isValid(ni, nj, n, m, board, ind, word) and (ni, nj) not in vis:
			vis.add((ni, nj))
			if helper(ni, nj, n, m, board, vis, text + board[ni][nj], ind + 1, word):
				return True
			vis.remove((ni, nj))

def isValid(i, j, n, m, board, ind, word):
	if i < n and i >= 0 and (j >= 0) and (j < m) and (ind < len(word)) and (board[i][j] == word[ind]):
		return True
	return False

class Solution:

	def isWordExist(self, board, word):
		return wordSearch(board, word)


class Solution:

	def adjacentSearch(self, board, word, i, j, l):
		if l == len(word):
			return True
		if i < 0 or j < 0 or i >= len(board) or (j >= len(board[0])):
			return False
		if board[i][j] != word[l]:
			return False
		board[i][j] = '*'
		ans = self.adjacentSearch(board, word, i - 1, j, l + 1) or self.adjacentSearch(board, word, i + 1, j, l + 1) or self.adjacentSearch(board, word, i, j - 1, l + 1) or self.adjacentSearch(board, word, i, j + 1, l + 1)
		board[i][j] = word[l]
		return ans

	def isWordExist(self, board, word):
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0] and self.adjacentSearch(board, word, i, j, 0):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):
		if not board:
			return
		m = len(board)
		n = len(board[0])
		dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		visited = set()

		def dfs(word, k, i, j):
			if word[k] == board[i][j]:
				visited.add((i, j))
				if len(visited) == len(word):
					return True
				for dir in dirs:
					newi = i + dir[0]
					newj = j + dir[1]
					if newi < len(board) and newi >= 0 and (newj < len(board[0])) and (newj >= 0) and ((newi, newj) not in visited):
						if dfs(word, k + 1, newi, newj):
							return True
				visited.remove((i, j))
				return False
		for i in range(m):
			for j in range(n):
				if dfs(word, 0, i, j):
					return 1
		return 0


def visit(board, word, curr, d, done, n, m, i, j):
	if curr == len(word):
		done[0] = True
		return
	dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	for (a, b) in dirs:
		if i + a >= 0 and j + b >= 0 and (i + a < n) and (j + b < m) and (word[curr] == board[i + a][j + b]):
			c = (i + a) * m + j + b
			if c not in d:
				d[c] = True
				visit(board, word, curr + 1, d, done, n, m, i + a, j + b)
				del d[c]

class Solution:

	def isWordExist(self, board, word):
		(n, m) = (len(board), len(board[0]))
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:
					d = {}
					done = [False]
					d[i * m + j] = True
					visit(board, word, 1, d, done, n, m, i, j)
					if done[0]:
						return True
		return False


class Solution:

	def isWordExist(self, board, word):
		ar1 = [-1, 0, 1, 0]
		ar2 = [0, 1, 0, -1]
		n = len(board)
		m = len(board[0])
		visit = [[0] * m for _ in range(n)]

		def dfs(i, j, visit, board, word, idx):
			if idx == len(word):
				return True
			if i < 0 or j < 0 or i >= n or (j >= m):
				return False
			if board[i][j] != word[idx]:
				return False
			if visit[i][j] == 1:
				return False
			visit[i][j] = 1
			for k in range(4):
				r1 = i + ar1[k]
				c1 = j + ar2[k]
				if dfs(r1, c1, visit, board, word, idx + 1):
					return True
			visit[i][j] = 0
			return False
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0] and dfs(i, j, visit, board, word, 0):
					return True
		return False


class Solution:

	def isWordExist(self, board, word):

		def recurs(c, i, j, grid):
			if c == '':
				return True
			elif i < 0 or i == len(board) or j < 0 or (j == len(board[0])):
				return False
			else:
				if grid[i][j] == c[0]:
					a = c[1:]
					m = grid[i][j]
					grid[i][j] = 0
					if recurs(a, i, j - 1, grid) or recurs(a, i, j + 1, grid) or recurs(a, i - 1, j, grid) or recurs(a, i + 1, j, grid):
						return True
					else:
						grid[i][j] = m
						return False
				return False
		for i in range(len(board)):
			for j in range(len(board[0])):
				if recurs(word, i, j, board):
					return True
		return False


from collections import deque

def isInside(i, j, n, m):
	if i >= 0 and i < n and (j >= 0) and (j < m):
		return True
	return False

def getAvailableNeighbors(i, j, n, m, grid, character):
	dx = [-1, 1, 0, 0]
	dy = [0, 0, 1, -1]
	avail = []
	for w in range(len(dy)):
		x = i + dx[w]
		y = j + dy[w]
		if isInside(x, y, n, m) and grid[x][y] == character:
			avail.append((x, y))
	return avail

def findWord(x, y, n, m, board, visited, wordStack, word, ix):
	wordStack.append(word[ix])
	visited[x][y] = True
	if ''.join(word) == ''.join(wordStack):
		return True
	if len(wordStack) == len(word):
		return False
	neigh = getAvailableNeighbors(x, y, n, m, board, word[ix + 1])
	for item in neigh:
		if board[item[0]][item[1]] == word[ix + 1]:
			if not visited[item[0]][item[1]]:
				if findWord(item[0], item[1], n, m, board, visited, wordStack, word, ix + 1):
					return True
	wordStack.pop()
	visited[x][y] = False

class Solution:

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		res = []
		found = False
		for x in range(n):
			for y in range(m):
				if board[x][y] == word[0]:
					visited = [[False] * m for i in range(n)]
					wordStack = []
					if findWord(x, y, n, m, board, visited, wordStack, word, 0):
						res.append(''.join(wordStack))
						found = True
						break
			if found:
				found = False
				break
		if len(res) > 0:
			return True
		return False


class Solution:

	def isWordExist(self, board, word):
		path = set()
		rows = len(board)
		cols = len(board[0])

		def solve(r, l, i, rows, cols, path, word, board):
			if i == len(word):
				return True
			if r < 0 or l < 0 or r >= rows or (l >= cols) or ((r, l) in path) or (word[i] != board[r][l]):
				return False
			path.add((r, l))
			ans = solve(r + 1, l, i + 1, rows, cols, path, word, board) or solve(r - 1, l, i + 1, rows, cols, path, word, board) or solve(r, l + 1, i + 1, rows, cols, path, word, board) or solve(r, l - 1, i + 1, rows, cols, path, word, board)
			path.remove((r, l))
			return ans
		for r in range(rows):
			for l in range(cols):
				if solve(r, l, 0, rows, cols, path, word, board) == True:
					return True
		return False


class Solution:

	def isWordExist(self, a, word):
		for r in range(len(a)):
			for c in range(len(a[0])):
				if a[r][c] == word[0] and self.search(a, r, c, word, 0):
					return True
		return False

	def search(self, a, r, c, word, ind):
		if ind == len(word):
			return True
		if r < 0 or r >= len(a) or c < 0 or (c >= len(a[0])) or (a[r][c] != word[ind]):
			return False
		temp = a[r][c]
		a[r][c] = ' '
		found = self.search(a, r + 1, c, word, ind + 1) or self.search(a, r - 1, c, word, ind + 1) or self.search(a, r, c + 1, word, ind + 1) or self.search(a, r, c - 1, word, ind + 1)
		a[r][c] = temp
		return found


class Solution:

	def DFSBackTracking(self, board, visited, row, col, word, index, n, m):
		if index == len(word):
			return True
		if row < 0 or row >= n or col < 0 or (col >= m) or (board[row][col] != word[index]) or visited[row][col]:
			return False
		visited[row][col] = True
		right = self.DFSBackTracking(board, visited, row, col + 1, word, index + 1, n, m)
		left = self.DFSBackTracking(board, visited, row, col - 1, word, index + 1, n, m)
		up = self.DFSBackTracking(board, visited, row - 1, col, word, index + 1, n, m)
		down = self.DFSBackTracking(board, visited, row + 1, col, word, index + 1, n, m)
		visited[row][col] = False
		return right or left or up or down

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		visited = [[False for col in range(m)] for row in range(n)]
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0] and visited[i][j] == False:
					if self.DFSBackTracking(board, visited, i, j, word, 0, n, m) == True:
						return True
		return False


class Solution:

	def isWordExist(self, l, s):
		(n, m) = (len(l), len(l[0]))
		v = set()
		dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

		def dfs(i, j, x):
			if x is '':
				return True
			if i < 0 or j < 0 or i == n or (j == m) or ((i, j) in v) or (l[i][j] != x[0]):
				return False
			f = False
			v.add((i, j))
			for (p, q) in dir:
				f = f or dfs(i + p, j + q, x[1:])
			v.remove((i, j))
			return f
		for i in range(n):
			for j in range(m):
				if l[i][j] == s[0]:
					if dfs(i, j, s):
						return True
		return False


from collections import deque

class Solution:

	def isWordExist(self, grid, word):
		(n, m) = (len(grid), len(grid[0]))
		x = set()

		def dfs(i, j, n, m, ind, s):
			if i < 0 or j < 0 or i >= n or (j >= m) or ((i, j) in v):
				return
			if s[ind] != grid[i][j]:
				return False
			if len(s) - 1 == ind:
				return True
			v.add((i, j))
			a = dfs(i + 1, j, n, m, ind + 1, s)
			b = dfs(i - 1, j, n, m, ind + 1, s)
			c = dfs(i, j + 1, n, m, ind + 1, s)
			d = dfs(i, j - 1, n, m, ind + 1, s)
			return a or b or c or d
		for i in range(n):
			for j in range(m):
				if grid[i][j] == word[0]:
					v = set()
					if dfs(i, j, n, m, 0, word):
						return True
		return False


class Solution:

	def dfs(self, row, col, idx, board, word, visited, R, C):
		if row >= 0 and row < R and (col >= 0) and (col < C) and (board[row][col] == word[idx]) and (not visited[row][col]):
			visited[row][col] = True
			dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
			for (dx, dy) in dxy:
				n_row = row + dx
				n_col = col + dy
				n_idx = idx + 1
				if n_idx == len(word):
					return True
				if self.dfs(n_row, n_col, n_idx, board, word, visited, R, C):
					return True
			visited[row][col] = False
		return False

	def isWordExist(self, board, word):
		R = len(board)
		C = len(board[0])
		visited = [[False for _ in range(C)] for _ in range(R)]
		for row in range(R):
			for col in range(C):
				if board[row][col] == word[0]:
					if self.dfs(row, col, 0, board, word, visited, R, C):
						return True
		return False


class Solution:

	def findword(self, board, word, i, j, k, vis):
		if k == len(word) - 1 and word[k] == board[i][j]:
			vis[i][j] = False
			return True
		ans = False
		if word[k] == board[i][j]:
			vis[i][j] = False
			li = vis
			if i - 1 >= 0 and vis[i - 1][j]:
				ans = ans or self.findword(board, word, i - 1, j, k + 1, li)
			if i + 1 < len(board) and vis[i + 1][j]:
				ans = ans or self.findword(board, word, i + 1, j, k + 1, li)
			if j - 1 >= 0 and vis[i][j - 1]:
				ans = ans or self.findword(board, word, i, j - 1, k + 1, li)
			if j + 1 < len(board[0]) and vis[i][j + 1]:
				ans = ans or self.findword(board, word, i, j + 1, k + 1, li)
		return ans

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:
					vis = [[True for j in range(m)] for i in range(n)]
					if self.findword(board, word, i, j, 0, vis):
						return True
		return False


class Solution:

	def isWordExist(self, board, word):

		def isValid(i, j, m, n, visited, board):
			if i < 0 or j < 0 or i >= m or (j >= n) or (visited[i][j] == 1):
				return 0
			return 1

		def help(m, n, i, j, idx, word, wlen, board, visited):
			if idx == wlen:
				return 1
			if isValid(i, j, m, n, visited, board):
				visited[i][j] = 1
				if word[idx] == board[i][j]:
					if help(m, n, i + 1, j, idx + 1, word, wlen, board, visited):
						return 1
					if help(m, n, i, j + 1, idx + 1, word, wlen, board, visited):
						return 1
					if help(m, n, i - 1, j, idx + 1, word, wlen, board, visited):
						return 1
					if help(m, n, i, j - 1, idx + 1, word, wlen, board, visited):
						return 1
				visited[i][j] = 0
			return 0
			return 0
		m = len(board)
		n = len(board[0])
		visited = []
		for i in range(m):
			visited.append([0] * n)
		setboard = set()
		setstring = set()
		for i in range(m):
			for j in range(n):
				setboard.add(board[i][j])
		for x in word:
			setstring.add(x)
		if not setstring.issubset(setboard):
			return 0
		for i in range(m):
			for j in range(n):
				if board[i][j] == word[0] and help(m, n, i, j, 0, word, len(word), board, visited):
					return 1
		return 0


class Solution:

	def isWordExist(self, board, word):
		(m, n) = (len(board), len(board[0]))
		visit = set()

		def dfs(x, y, l):
			if l == len(word):
				return True
			if x < 0 or x >= m or y < 0 or (y >= n) or (board[x][y] != word[l]) or ((x, y) in visit):
				return False
			visit.add((x, y))
			res = dfs(x + 1, y, l + 1) or dfs(x - 1, y, l + 1) or dfs(x, y + 1, l + 1) or dfs(x, y - 1, l + 1)
			visit.remove((x, y))
			return res
		for i in range(m):
			for j in range(n):
				if board[i][j] == word[0] and dfs(i, j, 0):
					return True
		return False


from collections import Counter

class Solution:

	def isWordExist(self, board, word):
		count = Counter(sum(board, []))
		if count[word[0]] > count[word[-1]]:
			word = word[::-1]
		for (ch, freq) in Counter(word).items():
			if count[ch] < freq:
				return 0

		def isValid(x, y):
			return 0 <= x < len(board) and 0 <= y < len(board[0])

		def dfs(i, j, index):
			if index == len(word):
				return 1
			char = board[i][j]
			board[i][j] = '#'
			for (offX, offY) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
				(nexti, nextj) = (i + offX, j + offY)
				if isValid(nexti, nextj) and board[nexti][nextj] == word[index] and (board[nexti][nextj] != '#'):
					if dfs(nexti, nextj, index + 1):
						return 1
			board[i][j] = char
			return 0
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0] and dfs(i, j, 1):
					return 1
		return 0


def validate(board, i, j, word):
	return i >= 0 and j >= 0 and (i < len(board)) and (j < len(board[0])) and (board[i][j] == word)

def sol(board, i, j, k, word):
	if k == len(word):
		return True
	if validate(board, i, j, word[k]):
		c = board[i][j]
		board[i][j] = '#'
		k = k + 1
		i = i + 1
		if sol(board, i, j, k, word):
			return True
		else:
			i = i - 1
		i = i - 1
		if sol(board, i, j, k, word):
			return True
		else:
			i = i + 1
		j = j + 1
		if sol(board, i, j, k, word):
			return True
		else:
			j = j - 1
		j = j - 1
		if sol(board, i, j, k, word):
			return True
		else:
			j = j + 1
		board[i][j] = c
		return False

class Solution:

	def isWordExist(self, board, word):
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					if sol(board, i, j, 0, word):
						return True
		return False


class Solution:

	def isWordExist(self, board, word):
		rw = len(board)
		cl = len(board[0])
		n = len(word)
		vis = {}
		res = [0]

		def dfs(r, c, i, cur):
			if i == n:
				if cur == word:
					return 1
			if r < 0 or r == rw or c < 0 or (c == cl) or (board[r][c] != word[i]) or (vis.get((r, c)) == 1):
				return 0
			vis[r, c] = 1
			x = dfs(r + 1, c, i + 1, cur + board[r][c]) or dfs(r - 1, c, i + 1, cur + board[r][c]) or dfs(r, c + 1, i + 1, cur + board[r][c]) or dfs(r, c - 1, i + 1, cur + board[r][c])
			vis[r, c] = 0
			return x
		for i in range(rw):
			for j in range(cl):
				if board[i][j] == word[0]:
					if dfs(i, j, 0, ''):
						return 1
		return 0


class Solution:

	def isWordExist(self, board, word):
		visited = [[0] * len(board[0]) for i in range(len(board))]
		delrow = [-1, 0, 1, 0]
		delcol = [0, 1, 0, -1]
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					if self.dfs(i, j, board, visited, 1, delrow, delcol):
						return True
		return False

	def dfs(self, row, col, board, visited, index, delrow, delcol):
		if index == len(word):
			return True
		visited[row][col] = 1
		for i in range(4):
			nr = row + delrow[i]
			nc = col + delcol[i]
			if nr >= 0 and nr < len(board) and (nc >= 0) and (nc < len(board[0])) and (visited[nr][nc] == 0) and (board[nr][nc] == word[index]):
				if self.dfs(nr, nc, board, visited, index + 1, delrow, delcol):
					return True
		visited[row][col] = 0
		return False


class Solution:

	def is_valid(self, x, y, visited, N, M):
		if x < 0 or y < 0 or x >= N or (y >= M) or (visited[x][y] == True):
			return False
		return True

	def DFS(self, node, graph, visited, word, letter):
		(u, v) = (node[0], node[1])
		if letter >= len(word):
			return True
		visited[node[0]][node[1]] = True
		for (x, y) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
			ch_x = x + u
			ch_y = y + v
			if self.is_valid(ch_x, ch_y, visited, len(graph), len(graph[0])) and graph[ch_x][ch_y] == word[letter]:
				if self.DFS([ch_x, ch_y], graph, visited, word, letter + 1):
					return True
		visited[node[0]][node[1]] = False
		return False

	def isWordExist(self, board, word):
		visited = [[False for i in range(len(board[0]))] for j in range(len(board))]
		for i in range(0, len(board)):
			for j in range(0, len(board[0])):
				if board[i][j] == word[0]:
					if self.DFS([i, j], board, visited, word, 1):
						return True
		return False


class Solution:

	def isWordExist(self, board, word):
		N = len(board)
		M = len(board[0])
		visited = [[False for j in range(M)] for i in range(N)]
		for i in range(N):
			for j in range(M):
				if board[i][j] == word[0] and (not visited[i][j]):
					if self.DFS(board, i, j, word, visited, 0):
						return True
		return False

	def DFS(self, board, i, j, word, visited, start):
		border_x = [-1, 0, 0, 1]
		border_y = [0, -1, 1, 0]
		visited[i][j] = True
		if word[start] != board[i][j] or start > len(word):
			visited[i][j] = False
			return False
		if word[start] == board[i][j] and start == len(word) - 1:
			return True
		for k in range(4):
			new_i = i + border_x[k]
			new_j = j + border_y[k]
			if self.isSafe(board, new_i, new_j, visited):
				ans = self.DFS(board, new_i, new_j, word, visited, start + 1)
				if ans:
					return True
		visited[i][j] = False
		return False

	def isSafe(self, board, i, j, visited):
		return 0 <= i < len(board) and 0 <= j < len(board[0]) and (not visited[i][j])


class Solution:

	def find(self, i, j, board, vi, word, c, n, m):
		if i >= n or j >= m or i < 0 or (j < 0):
			return False
		if vi[i][j]:
			return False
		if c == len(word):
			return True
		vi[i][j] = True
		if board[i][j] == word[c]:
			if self.find(i, j + 1, board, vi, word, c + 1, n, m) or self.find(i, j - 1, board, vi, word, c + 1, n, m) or self.find(i + 1, j, board, vi, word, c + 1, n, m) or self.find(i - 1, j, board, vi, word, c + 1, n, m):
				return True
		vi[i][j] = False
		return False

	def isWordExist(self, board, word):
		vi = []
		n = len(board)
		m = len(board[0])
		for i in range(n):
			l = [False] * m
			vi.append(l)
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:
					if self.find(i, j, board, vi, word, 0, n, m):
						return True
		return False


class Solution:

	def isWordExist(self, board, word):
		n = len(board)
		m = len(board[0])

		def dfs(i, j, n, m, L, vis, ind):
			vis.add((i, j))
			if ind == L:
				return True
			for (u, v) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
				ro = i + u
				co = j + v
				if ro > -1 and co > -1 and (ro < n) and (co < m) and (board[ro][co] == word[ind]) and ((ro, co) not in vis):
					if dfs(ro, co, n, m, L, vis, ind + 1):
						return True
			vis.discard((i, j))
			return False
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:
					if dfs(i, j, n, m, len(word), set(), 1):
						return True
		return False


class Solution:

	def isWordExist(self, board, word):
		l = len(word)
		grid = board
		(n, m) = (len(grid), len(grid[0]))

		def dfs(i, j, l, ind):
			nonlocal vis
			if ind == l:
				return 1
			(x, y, z, w) = (0, 0, 0, 0)
			vis[i][j] = 1
			if i + 1 < n and grid[i + 1][j] == word[ind] and (vis[i + 1][j] == 0):
				x = dfs(i + 1, j, l, ind + 1)
			if j + 1 < m and grid[i][j + 1] == word[ind] and (vis[i][j + 1] == 0):
				y = dfs(i, j + 1, l, ind + 1)
			if i - 1 >= 0 and grid[i - 1][j] == word[ind] and (vis[i - 1][j] == 0):
				z = dfs(i - 1, j, l, ind + 1)
			if j - 1 >= 0 and grid[i][j - 1] == word[ind] and (vis[i][j - 1] == 0):
				w = dfs(i, j - 1, l, ind + 1)
			return x or z or y or w
		for i in range(n):
			for j in range(m):
				if grid[i][j] == word[0]:
					vis = [[0 for x in range(m)] for j in range(n)]
					if dfs(i, j, l, 1):
						return True
		return False


class Solution:

	def solve(self, i, j, word, board, n1, n2, index):
		found = 0
		if i < n1 and j < n2 and (i >= 0) and (j >= 0) and (word[index] == board[i][j]):
			temp = word[index]
			board[i][j] = 0
			index += 1
			if index == len(word):
				found = 1
			else:
				found += self.solve(i + 1, j, word, board, n1, n2, index)
				found += self.solve(i - 1, j, word, board, n1, n2, index)
				found += self.solve(i, j + 1, word, board, n1, n2, index)
				found += self.solve(i, j - 1, word, board, n1, n2, index)
			board[i][j] = temp
		return found

	def isWordExist(self, board, word):
		result = 0
		n1 = len(board)
		n2 = len(board[0])
		for i in range(n1):
			for j in range(n2):
				result += self.solve(i, j, word, board, n1, n2, 0)
		return result


def func(pos, board, word, visted, ans):
	(i, j) = pos
	if i < 0 or j < 0 or i >= len(board) or (j >= len(board[0])) or (visted[i][j] == True) or (len(word) == 0) or (board[i][j] != word[0]):
		return
	visted[i][j] = True
	if len(word) == 1:
		ans[0] = 1
		return
	func((i, j + 1), board, word[1:], visted, ans)
	func((i + 1, j), board, word[1:], visted, ans)
	func((i, j - 1), board, word[1:], visted, ans)
	func((i - 1, j), board, word[1:], visted, ans)
	visted[i][j] = False

class Solution:

	def isWordExist(self, board, word):
		visted = [[False for i in range(len(board[0]))] for i in range(len(board))]
		ans = [0]
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					func((i, j), board, word, visted, ans)
		return ans[0]