Find the number of occurrences of a given search word in a 2d-Array of characters where the word can go up, down, left, right, and around 90-degree bends.
Note: While making a word you can use one cell only once.
Example 1:
Input: 
R = 4, C = 5
mat = {{S,N,B,S,N},
       {B,A,K,E,A},
       {B,K,B,B,K},
       {S,E,B,S,E}}
target = SNAKES
Output:
3
Explanation: 
S N B S N
B A K E A
B K B B K
S E B S E
Total occurrence of the word is 3
and denoted by color.
Example 2:
Input:
R = 3, C = 3 
mat = {{c,a,t},
       {a,t,c},
       {c,t,a}}
target = cat
Output:
5
Explanation: Same explanation
as first example.
Your task:
You don't need to read input or print anything. Your task is to complete the function findOccurrence() which takes the mat containing N*M 2-d array of characters and target as input parameters and returns the number of occurrences of the target.
Expected Time Complexity: O(R*C*2^{2*len}), Where len is the length of the target String.
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ len ≤ 15
1 ≤ R, C ≤ 50

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def findOccurrence(self,mat,target):

Solutions:
class Solution:

	def internalSearch(self, idx, target, r, c, mat, max_row, max_col):
		found = 0
		if (r >= 0 and r <= max_row) and (c >= 0 and c <= max_col) and (target[idx] == mat[r][c]):
			match = target[idx]
			idx += 1
			mat[r][c] = 0
			if idx == len(target):
				found = 1
			else:
				found += self.internalSearch(idx, target, r, c + 1, mat, max_row, max_col)
				found += self.internalSearch(idx, target, r, c - 1, mat, max_row, max_col)
				found += self.internalSearch(idx, target, r + 1, c, mat, max_row, max_col)
				found += self.internalSearch(idx, target, r - 1, c, mat, max_row, max_col)
			mat[r][c] = match
		return found

	def findOccurrence(self, mat, target):
		res = 0
		row_count = len(mat)
		col_count = len(mat[0])
		for r in range(row_count):
			for c in range(col_count):
				res += self.internalSearch(0, target, r, c, mat, row_count - 1, col_count - 1)
		return res


class Solution:

	def __init__(self):
		self.ans = 0

	def findOccurrence(self, mat, target):

		def backtrack(grid, target, r, c, i, j, x):
			if i >= r or j >= c or i < 0 or (j < 0) or (grid[i][j] != target[x]):
				return
			if x == len(target) - 1:
				self.ans += 1
				return
			if grid[i][j] == target[x]:
				x += 1
				temp = grid[i][j]
				grid[i][j] = '#'
				backtrack(grid, target, r, c, i + 1, j, x)
				backtrack(grid, target, r, c, i - 1, j, x)
				backtrack(grid, target, r, c, i, j + 1, x)
				backtrack(grid, target, r, c, i, j - 1, x)
				grid[i][j] = temp
				x -= 1
		r = len(mat)
		c = len(mat[0])
		for i in range(r):
			for j in range(c):
				if mat[i][j] == target[0]:
					backtrack(mat, target, r, c, i, j, 0)
		return self.ans


class Solution:

	def findOccurrence(self, grid, s):
		(n, m) = (len(grid), len(grid[0]))
		(o, v) = (len(s), set())

		def dfs(i, j, k, n, m, o):
			if i < 0 or j < 0 or i >= n or (j >= m) or (grid[i][j] != s[k]) or ((i, j) in v):
				return 0
			if k == o - 1:
				return 1
			v.add((i, j))
			l = dfs(i, j - 1, k + 1, n, m, o)
			r = dfs(i, j + 1, k + 1, n, m, o)
			u = dfs(i - 1, j, k + 1, n, m, o)
			d = dfs(i + 1, j, k + 1, n, m, o)
			v.remove((i, j))
			return l + r + u + d
		c = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == s[0]:
					v = set()
					c += dfs(i, j, 0, n, m, o)
		return c


from collections import defaultdict

class Solution:
	adjs = [0, 1, 0, -1, 0]

	def findOccurrence(self, mat, target):
		R = len(mat)
		C = len(mat[0])
		cnt = 0
		for i in range(R):
			for j in range(C):
				cnt += self.dupDfs(mat, i, j, target)
		return cnt

	def dupDfs(self, mat, r, c, word, stk=defaultdict(bool), i=0):
		if word[i] != mat[r][c]:
			return 0
		if i == len(word) - 1:
			return 1
		stk[r, c] = True
		res = 0
		for k in range(4):
			(ad_r, ad_c) = (r + self.adjs[k], c + self.adjs[k + 1])
			if ad_r < 0 or ad_c < 0 or ad_r == len(mat) or (ad_c == len(mat[0])):
				continue
			if stk[ad_r, ad_c]:
				continue
			res += self.dupDfs(mat, ad_r, ad_c, word, stk, i + 1)
		stk[r, c] = False
		return res


class Solution:

	def findOccurrence(self, mat, target):
		r = len(mat)
		c = len(mat[0])
		count = [0]

		def dfs(mat, i, j, target, k, count):
			if i < 0 or j < 0 or i >= r or (j >= c) or (mat[i][j] != target[k]):
				return
			if len(target) - 1 == k:
				count[0] += 1
				return
			temp = mat[i][j]
			mat[i][j] = '*'
			dfs(mat, i + 1, j, target, k + 1, count)
			dfs(mat, i - 1, j, target, k + 1, count)
			dfs(mat, i, j - 1, target, k + 1, count)
			dfs(mat, i, j + 1, target, k + 1, count)
			mat[i][j] = temp
		for i in range(r):
			for j in range(c):
				if mat[i][j] == target[0]:
					dfs(mat, i, j, target, 0, count)
		return count[0]


class Solution:

	def findOccurrence(self, mat, target):

		def cnt(len_str, r, c, rmax, cmax):
			found = 0
			if r < rmax and c < cmax and (r > -1) and (c > -1) and (target[len_str] == mat[r][c]):
				match = target[len_str]
				len_str += 1
				mat[r][c] = 0
				if len_str == len(target):
					found = 1
				else:
					found += cnt(len_str, r, c + 1, rmax, cmax)
					found += cnt(len_str, r, c - 1, rmax, cmax)
					found += cnt(len_str, r + 1, c, rmax, cmax)
					found += cnt(len_str, r - 1, c, rmax, cmax)
				mat[r][c] = match
			return found
		found = 0
		R = len(mat)
		C = len(mat[0])
		for i in range(R):
			for j in range(C):
				found = found + cnt(0, i, j, R, C)
		return found


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def __init__(self):
		self.count = 0

	def helper(self, mat, i, j, k, target, stack):
		if k == len(target):
			self.count += 1
			return
		stack.add((i, j))
		(r, c) = (len(mat), len(mat[0]))
		if i - 1 >= 0 and mat[i - 1][j] == target[k] and ((i - 1, j) not in stack):
			self.helper(mat, i - 1, j, k + 1, target, stack)
		if j - 1 >= 0 and mat[i][j - 1] == target[k] and ((i, j - 1) not in stack):
			self.helper(mat, i, j - 1, k + 1, target, stack)
		if i + 1 < r and mat[i + 1][j] == target[k] and ((i + 1, j) not in stack):
			self.helper(mat, i + 1, j, k + 1, target, stack)
		if j + 1 < c and mat[i][j + 1] == target[k] and ((i, j + 1) not in stack):
			self.helper(mat, i, j + 1, k + 1, target, stack)
		stack.remove((i, j))

	def findOccurrence(self, mat, target):
		(r, c) = (len(mat), len(mat[0]))
		stack = set()
		count = 0
		for i in range(r):
			for j in range(c):
				if mat[i][j] == target[0]:
					self.helper(mat, i, j, 1, target, stack)
		return self.count


def rec(mat, target, i, j, visited, ind):
	if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])) or visited[i][j] or (mat[i][j] != target[ind]):
		return 0
	if ind == len(target) - 1 and target[ind] == mat[i][j]:
		return 1
	ans = 0
	visited[i][j] = True
	ans += rec(mat, target, i + 1, j, visited, ind + 1)
	ans += rec(mat, target, i - 1, j, visited, ind + 1)
	ans += rec(mat, target, i, j + 1, visited, ind + 1)
	ans += rec(mat, target, i, j - 1, visited, ind + 1)
	visited[i][j] = False
	return ans

class Solution:

	def findOccurrence(self, mat, target):
		ans = 0
		visited = [[0 for i in range(len(mat[0]))] for j in range(len(mat))]
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				ans += rec(mat, target, i, j, visited, 0)
		return ans


class Solution:

	def findOccurrence(self, arr, s):
		rowlen = len(arr)
		collen = len(arr[0])
		no = 0
		for row in range(rowlen):
			for col in range(collen):
				no += self.search(0, arr, s, row, col, rowlen, collen)
		return no

	def search(self, i, arr, s, row, col, rowlen, collen):
		ans = 0
		if row >= 0 and row < rowlen and (col >= 0) and (col < collen) and (arr[row][col] == s[i]):
			char = arr[row][col]
			arr[row][col] = 0
			i += 1
			if i == len(s):
				ans = 1
				arr[row][col] = char
				return ans
			ans += self.search(i, arr, s, row + 1, col, rowlen, collen)
			ans += self.search(i, arr, s, row, col + 1, rowlen, collen)
			ans += self.search(i, arr, s, row - 1, col, rowlen, collen)
			ans += self.search(i, arr, s, row, col - 1, rowlen, collen)
			arr[row][col] = char
		return ans


finding = 0
v = 0

def find(mat, target, i, j, curr, dp):
	global finding
	global v
	if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])) or (dp[i][j] == 1):
		return 0
	elif curr == len(target) - 1:
		if mat[i][j] == target[curr] and dp[i][j] != 1:
			finding = finding + 1
		return 0
	elif mat[i][j] != target[curr]:
		return 0
	elif mat[i][j] == target[curr]:
		dp[i][j] = 1
		find(mat, target, i, j + 1, curr + 1, dp)
		find(mat, target, i, j - 1, curr + 1, dp)
		find(mat, target, i + 1, j, curr + 1, dp)
		find(mat, target, i - 1, j, curr + 1, dp)
		dp[i][j] = 0

class Solution:

	def findOccurrence(self, mat, target):
		global finding
		dp = []
		global v
		for i in range(0, len(mat)):
			p = []
			for j in range(0, len(mat[0])):
				p.append(0)
			dp.append(p)
		z = 0
		for i in range(0, len(mat)):
			for j in range(0, len(mat[0])):
				find(mat, target, i, j, 0, dp)
				z = z + finding
				v = v + 1
				finding = 0
		return z


class Solution:

	def findOccurrence(self, mat, target):
		n = len(mat)
		m = len(mat[0])
		queue = []

		def findword(mat, target, i, j, currentindex):
			if i < 0 or j < 0 or i >= n or (j >= m):
				return 0
			curchar = mat[i][j]
			if target[currentindex] != curchar:
				return 0
			if currentindex == len(target) - 1:
				return 1
			mat[i][j] = '\x00'
			count = 0
			count += findword(mat, target, i - 1, j, currentindex + 1)
			count += findword(mat, target, i + 1, j, currentindex + 1)
			count += findword(mat, target, i, j - 1, currentindex + 1)
			count += findword(mat, target, i, j + 1, currentindex + 1)
			mat[i][j] = curchar
			return count
		for i in range(n):
			for j in range(m):
				if mat[i][j] == target[0]:
					queue.append((i, j))
		cnt = 0
		for i in range(n):
			for j in range(m):
				cnt += findword(mat, target, i, j, 0)
		return cnt


class Solution:

	def findWord(self, mat, target, i, j, curind):
		if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])):
			return 0
		curchar = mat[i][j]
		if target[curind] != curchar:
			return 0
		if curind == len(target) - 1:
			return 1
		count = 0
		mat[i][j] = None
		count = count + self.findWord(mat, target, i - 1, j, curind + 1)
		count = count + self.findWord(mat, target, i + 1, j, curind + 1)
		count = count + self.findWord(mat, target, i, j + 1, curind + 1)
		count = count + self.findWord(mat, target, i, j - 1, curind + 1)
		mat[i][j] = curchar
		return count

	def findOccurrence(self, mat, target):
		count = 0
		for i in range(0, len(mat)):
			for j in range(0, len(mat[0])):
				count = count + self.findWord(mat, target, i, j, 0)
		return count


class Solution:

	def findWord(self, mat, target, i, j, curIndex):
		if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])):
			return 0
		curChar = mat[i][j]
		if target[curIndex] != curChar:
			return 0
		if curIndex == len(target) - 1:
			return 1
		count = 0
		mat[i][j] = None
		count += self.findWord(mat, target, i - 1, j, curIndex + 1)
		count += self.findWord(mat, target, i + 1, j, curIndex + 1)
		count += self.findWord(mat, target, i, j + 1, curIndex + 1)
		count += self.findWord(mat, target, i, j - 1, curIndex + 1)
		mat[i][j] = curChar
		return count

	def findOccurrence(self, mat, target):
		count = 0
		for i in range(0, len(mat)):
			for j in range(0, len(mat[0])):
				count += self.findWord(mat, target, i, j, 0)
		return count


class Solution:

	def findOccurrence(self, mat, target):

		def count(len_str, row, col, row_max, col_max):
			found = 0
			if row < row_max and col < col_max and (col > -1) and (row > -1) and (target[len_str] == mat[row][col]):
				match = target[len_str]
				len_str = len_str + 1
				mat[row][col] = 0
				if len_str == len(target):
					found = 1
				else:
					found = found + count(len_str, row, col + 1, row_max, col_max)
					found = found + count(len_str, row, col - 1, row_max, col_max)
					found = found + count(len_str, row + 1, col, row_max, col_max)
					found = found + count(len_str, row - 1, col, row_max, col_max)
				mat[row][col] = match
			return found
		found = 0
		R = len(mat)
		C = len(mat[0])
		for i in range(R):
			for j in range(C):
				found = found + count(0, i, j, R, C)
		return found


class Solution:

	def findOccurrence(self, mat, target):
		cnt = 0
		(m, n) = (len(mat), len(mat[0]))
		seen = set()

		def dfs(r, c, target):
			nonlocal cnt, m, n
			if not target:
				cnt += 1
				return
			if r < 0 or r >= m or c < 0 or (c >= n) or ((r, c) in seen) or (mat[r][c] != target[0]):
				return
			seen.add((r, c))
			dfs(r + 1, c, target[1:])
			dfs(r - 1, c, target[1:])
			dfs(r, c + 1, target[1:])
			dfs(r, c - 1, target[1:])
			seen.remove((r, c))
		for r in range(len(mat)):
			for c in range(len(mat[0])):
				if mat[r][c] != target[0]:
					continue
				dfs(r, c, target)
		return cnt // 4


class Solution:

	def findOccurrence(self, mat, target):
		walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		m = len(mat)
		n = len(mat[0])
		res = 0

		def find_str(x, y, mat, index):
			if not (x >= 0 and x < m and (y >= 0) and (y < n)):
				return 0
			if mat[x][y] != target[index]:
				return 0
			if index == len(target) - 1:
				return 1
			mat[x][y] = 0
			found = 0
			for (dx, dy) in walk:
				new_x = x + dx
				new_y = y + dy
				found += find_str(new_x, new_y, mat, index + 1)
			mat[x][y] = target[index]
			return found
		for i in range(m):
			for j in range(n):
				if mat[i][j] == target[0]:
					res += find_str(i, j, mat, 0)
		return res


class Solution:

	def isValid(self, x, y, n, m):
		if x >= 0 and y >= 0 and (x < n) and (y < m):
			return True
		return False

	def solve(self, mat, tar, i, j, ind, n, m, X, Y):
		global cnt
		if ind == len(tar):
			cnt += 1
			return
		if not (self.isValid(i, j, n, m) and mat[i][j] == tar[ind]):
			return
		temp = mat[i][j]
		mat[i][j] = '$'
		for points in range(4):
			nx = i + X[points]
			ny = j + Y[points]
			self.solve(mat, tar, nx, ny, ind + 1, n, m, X, Y)
		mat[i][j] = temp

	def findOccurrence(self, mat, tar):
		n = len(mat)
		m = len(mat[0])
		global cnt
		cnt = 0
		X = [0, 0, 1, -1]
		Y = [1, -1, 0, 0]
		for i in range(n):
			for j in range(m):
				if mat[i][j] == tar[0]:
					self.solve(mat, tar, i, j, 0, n, m, X, Y)
		return cnt // 4


class Solution:

	def findOccurrence(self, mat, target):
		row = len(mat)
		col = len(mat[0])
		found = 0
		for i in range(row):
			for j in range(col):
				found = found + self.findOccurenceWord(0, target, mat, i, j, row - 1, col - 1)
		return found

	def findOccurenceWord(self, index, target, mat, row, col, row_max, col_max):
		found = 0
		if row >= 0 and row <= row_max and (col >= 0) and (col <= col_max) and (target[index] == mat[row][col]):
			currentWord = target[index]
			index = index + 1
			mat[row][col] = 0
			if index == len(target):
				found = 1
			else:
				found = found + self.findOccurenceWord(index, target, mat, row, col - 1, row_max, col_max)
				found = found + self.findOccurenceWord(index, target, mat, row, col + 1, row_max, col_max)
				found = found + self.findOccurenceWord(index, target, mat, row - 1, col, row_max, col_max)
				found = found + self.findOccurenceWord(index, target, mat, row + 1, col, row_max, col_max)
			mat[row][col] = currentWord
		return found


class Solution:

	def dfs(self, visited, mat, target, index, i, j, n, m, n_target):
		if index >= n_target:
			return 1
		c1 = 0
		c2 = 0
		c3 = 0
		c4 = 0
		if i - 1 >= 0 and visited[i - 1][j] == 0 and (index < n_target) and (mat[i - 1][j] == target[index]):
			visited[i - 1][j] = 1
			c1 = self.dfs(visited, mat, target, index + 1, i - 1, j, n, m, n_target)
			visited[i - 1][j] = 0
		if j + 1 < m and visited[i][j + 1] == 0 and (index < n_target) and (mat[i][j + 1] == target[index]):
			visited[i][j + 1] = 1
			c2 = self.dfs(visited, mat, target, index + 1, i, j + 1, n, m, n_target)
			visited[i][j + 1] = 0
		if i + 1 < n and visited[i + 1][j] == 0 and (index < n_target) and (mat[i + 1][j] == target[index]):
			visited[i + 1][j] = 1
			c3 = self.dfs(visited, mat, target, index + 1, i + 1, j, n, m, n_target)
			visited[i + 1][j] = 0
		if j - 1 >= 0 and visited[i][j - 1] == 0 and (index < n_target) and (mat[i][j - 1] == target[index]):
			visited[i][j - 1] = 1
			c4 = self.dfs(visited, mat, target, index + 1, i, j - 1, n, m, n_target)
			visited[i][j - 1] = 0
		return c1 + c2 + c3 + c4

	def findOccurrence(self, mat, target):
		n = len(mat)
		m = len(mat[0])
		count = 0
		visited = [[0] * m for i in range(n)]
		for i in range(n):
			for j in range(m):
				if mat[i][j] == target[0]:
					visited[i][j] = 1
					count += self.dfs(visited, mat, target, 1, i, j, n, m, len(target))
					visited[i][j] = 0
		return count


def bt(target, mat, r, c):
	total = []
	if len(target) == 1:
		for i in range(r):
			for j in range(c):
				if mat[i][j] == target:
					total.append('a')
	for i in range(r):
		for j in range(c):
			ind = 1
			if target[0] == mat[i][j]:
				temp = [(i, j)]
				vis = set()
				vis.add((i, j))
				helper(i, j, r, c, vis, ind, target, mat, 'S', temp, total)
	return len(total)

def helper(i, j, r, c, vis, ind, target, mat, text, temp, total):
	for neigh in neighbors(i, j, r, c):
		(n_i, n_j) = (neigh[0], neigh[1])
		if (n_i, n_j) not in vis and ind < len(target) and (target[ind] == mat[n_i][n_j]):
			vis.add((n_i, n_j))
			ind += 1
			text += mat[n_i][n_j]
			temp.append((n_i, n_j))
			if len(target) == len(vis):
				total.append('a')
			helper(n_i, n_j, r, c, vis, ind, target, mat, text, temp, total)
			ind -= 1
			temp.remove((n_i, n_j))
			vis.remove((n_i, n_j))

def neighbors(i, j, r, c):
	stack = []
	if i + 1 < r:
		stack.append((i + 1, j))
	if i - 1 >= 0:
		stack.append((i - 1, j))
	if j - 1 >= 0:
		stack.append((i, j - 1))
	if j + 1 < c:
		stack.append((i, j + 1))
	return stack

class Solution:

	def findOccurrence(self, mat, target):
		(r, c) = (len(mat), len(mat[0]))
		res = bt(target, mat, r, c)
		return res


class Solution:

	def findOccurrence(self, mat, target):
		r = len(mat)
		c = len(mat[0])
		n = len(target) - 1

		def dfs(i, j, k):
			if i < 0 or i >= r or j < 0 or (j >= c) or (mat[i][j] != target[k]):
				return 0
			if k == n:
				return 1
			cnt = 0
			store = mat[i][j]
			mat[i][j] = '*'
			cnt += dfs(i + 1, j, k + 1)
			cnt += dfs(i - 1, j, k + 1)
			cnt += dfs(i, j + 1, k + 1)
			cnt += dfs(i, j - 1, k + 1)
			mat[i][j] = store
			return cnt
		ans = 0
		for i in range(r):
			for j in range(c):
				ans += dfs(i, j, 0)
		return ans


class Solution:

	def findOccurrence(self, mat, target):
		(m, n) = (len(mat), len(mat[0]))
		s = len(target)
		ans = [0]
		visited = set()

		def backtrack(i, j, widx):
			if i < 0 or j < 0 or i >= m or (j >= n) or (widx > s) or ((i, j) in visited) or (mat[i][j] != target[widx]):
				return
			if widx == s - 1:
				ans[0] += 1
				return
			visited.add((i, j))
			backtrack(i, j + 1, widx + 1)
			backtrack(i + 1, j, widx + 1)
			backtrack(i, j - 1, widx + 1)
			backtrack(i - 1, j, widx + 1)
			visited.remove((i, j))
		for i in range(m):
			for j in range(n):
				if mat[i][j] == target[0]:
					backtrack(i, j, 0)
		return ans[0]


class Solution:

	def findOccurrence(self, mat, target):

		def recursion(r, c, ind):
			if r >= row or c >= col or r < 0 or (c < 0) or (mat[r][c] != target[ind]):
				return 0
			if ind == len(target) - 1:
				count[0] += 1
				return 1
			temp = mat[r][c]
			mat[r][c] = '*'
			recursion(r + 1, c, ind + 1)
			recursion(r, c + 1, ind + 1)
			recursion(r - 1, c, ind + 1)
			recursion(r, c - 1, ind + 1)
			mat[r][c] = temp
		row = len(mat)
		col = len(mat[0])
		count = [0]
		for r in range(row):
			for c in range(col):
				if mat[r][c] == target[0]:
					recursion(r, c, 0)
		return count[0]


class Solution:

	def findOccurrence(self, mat, target):

		def dfs(i, j, ind):
			if i < 0 or j < 0 or i >= row or (j >= col) or (mat[i][j] != target[ind]):
				return 0
			if ind == len(target) - 1:
				count[0] += 1
				return
			temp = mat[i][j]
			mat[i][j] = '*'
			for dir in directions:
				dfs(i + dir[0], j + dir[1], ind + 1)
			mat[i][j] = temp
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		count = [0]
		row = len(mat)
		col = len(mat[0])
		for r in range(row):
			for c in range(col):
				if mat[r][c] == target[0]:
					if dfs(r, c, 0):
						break
		return count[0]


class Solution:

	def findOccurrence(self, mat, target):
		m = len(mat)
		n = len(mat[0])
		l = len(target)
		sum = 0

		def countOccurences(i, j, target, index):
			found = 0
			if i < 0 or j < 0 or i > m - 1 or (j > n - 1) or (mat[i][j] != target[index]):
				return 0
			if index == l - 1 and mat[i][j] == target[l - 1]:
				return 1
			mat[i][j] = '#'
			found += countOccurences(i, j + 1, target, index + 1)
			found += countOccurences(i, j - 1, target, index + 1)
			found += countOccurences(i + 1, j, target, index + 1)
			found += countOccurences(i - 1, j, target, index + 1)
			mat[i][j] = target[index]
			return found
		for i in range(m):
			for j in range(n):
				if mat[i][j] == target[0]:
					sum += countOccurences(i, j, target, 0)
		return sum


class Solution:

	def findWordCount(self, i, j, n, m, mat, target, k, ind):
		found = 0
		if i >= 0 and j >= 0 and (i < n) and (j < m) and (target[ind] == mat[i][j]):
			temp = mat[i][j]
			mat[i][j] = '$'
			ind += 1
			if ind == k:
				found = 1
			else:
				found += self.findWordCount(i - 1, j, n, m, mat, target, k, ind)
				found += self.findWordCount(i + 1, j, n, m, mat, target, k, ind)
				found += self.findWordCount(i, j - 1, n, m, mat, target, k, ind)
				found += self.findWordCount(i, j + 1, n, m, mat, target, k, ind)
			mat[i][j] = temp
		return found

	def findOccurrence(self, mat, target):
		(n, m) = (len(mat), len(mat[0]))
		k = len(target)
		ans = 0
		for i in range(n):
			for j in range(m):
				ans += self.findWordCount(i, j, n, m, mat, target, k, 0)
		return ans


class Solution:

	def findOccurrence(self, mat, target):
		row = len(mat)
		col = len(mat[0])
		count = [0]

		def dfs(mat, i, j, target, k, count):
			if i < 0 or j < 0 or i >= row or (j >= col) or (mat[i][j] != target[k]):
				return
			if len(target) - 1 == k:
				count[0] += 1
				return
			temp = mat[i][j]
			mat[i][j] = ' '
			dfs(mat, i + 1, j, target, k + 1, count)
			dfs(mat, i - 1, j, target, k + 1, count)
			dfs(mat, i, j - 1, target, k + 1, count)
			dfs(mat, i, j + 1, target, k + 1, count)
			mat[i][j] = temp
		for i in range(row):
			for j in range(col):
				if mat[i][j] == target[0]:
					dfs(mat, i, j, target, 0, count)
		return count[0]


count = 0

class Solution:

	def findOccurrence(self, mat, target):
		global count

		def generate(row, col, current):
			global count
			if current == len(target):
				count += 1
			elif (row >= 0 and row < len(mat)) and (col >= 0 and col < len(mat[0])):
				if mat[row][col] == target[current]:
					p = mat[row][col]
					mat[row][col] = -1
					generate(row + 1, col, current + 1)
					generate(row - 1, col, current + 1)
					generate(row, col + 1, current + 1)
					generate(row, col - 1, current + 1)
					mat[row][col] = p
				else:
					return
			else:
				return
		count = 0
		for i in range(len(mat)):
			for j in range(len(mat[i])):
				if mat[i][j] == target[0]:
					generate(i, j, 0)
		return int(count / 4)


class Solution:

	def inside(self, grid, i, j):
		if i in range(len(grid)) and j in range(len(grid[0])):
			return True
		return False

	def dfs(self, grid, i, j, val, index, full_string, max_index, visited):
		if not self.inside(grid, i, j) or visited[i][j] == True or grid[i][j] != val:
			return 0
		if grid[i][j] == val:
			index += 1
			if index >= max_index:
				return 1
			if index < max_index:
				val = full_string[index]
				visited[i][j] = True
				left = self.dfs(grid, i, j - 1, val, index, full_string, max_index, visited)
				top = self.dfs(grid, i - 1, j, val, index, full_string, max_index, visited)
				right = self.dfs(grid, i, j + 1, val, index, full_string, max_index, visited)
				bottom = self.dfs(grid, i + 1, j, val, index, full_string, max_index, visited)
				visited[i][j] = False
				return left + top + right + bottom

	def findOccurrence(self, mat, target):
		ans = 0
		grid = mat
		visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == target[0]:
					val = target[0]
					max_index = len(target)
					index = 0
					full_string = target
					ans += self.dfs(grid, i, j, val, index, full_string, max_index, visited)
		return ans


class Solution:

	def findOccurrence(self, board, word):
		n = len(board)
		m = len(board[0])
		k = len(word)
		d = 0
		for i in range(n):
			for j in range(m):
				if board[i][j] == word[0]:

					def dfs(i, j, c):
						if c == k - 1 and i >= 0 and (i < n) and (j >= 0) and (j < m):
							if board[i][j] == word[c]:
								return 1
							return 0
						if i < 0 or j < 0 or i >= n or (j >= m):
							return 0
						if board[i][j] != word[c]:
							return 0
						temp = board[i][j]
						board[i][j] = '*'
						g = dfs(i + 1, j, c + 1) + dfs(i - 1, j, c + 1) + dfs(i, j + 1, c + 1) + dfs(i, j - 1, c + 1)
						board[i][j] = temp
						return g
					d += dfs(i, j, 0)
		return d


class Solution:

	def findOccurrence(self, mat, target):
		m = len(mat)
		n = len(mat[0])
		(new_pos, pos) = ([], [])
		for (k, c) in enumerate(target):
			new_pos = []
			if k == 0:
				for i in range(m):
					for j in range(n):
						if mat[i][j] == c:
							new_pos.append(({(i, j): 0}, (i, j)))
			else:
				for (solution, coord) in pos:
					(i, j) = coord
					if i > 0 and mat[i - 1][j] == c and ((i - 1, j) not in solution):
						new_s = solution.copy()
						new_s[i - 1, j] = new_s[i, j] + 1
						new_pos.append((new_s, (i - 1, j)))
					if j > 0 and mat[i][j - 1] == c and ((i, j - 1) not in solution):
						new_s = solution.copy()
						new_s[i, j - 1] = new_s[i, j] + 1
						new_pos.append((new_s, (i, j - 1)))
					if i < m - 1 and mat[i + 1][j] == c and ((i + 1, j) not in solution):
						new_s = solution.copy()
						new_s[i + 1, j] = new_s[i, j] + 1
						new_pos.append((new_s, (i + 1, j)))
					if j < n - 1 and mat[i][j + 1] == c and ((i, j + 1) not in solution):
						new_s = solution.copy()
						new_s[i, j + 1] = new_s[i, j] + 1
						new_pos.append((new_s, (i, j + 1)))
			pos = new_pos
		return len(pos)


class Solution:

	def findOccurrence(self, mat, target):

		def func(i, j, ind):
			if i < 0 or i >= m or j < 0 or (j >= n) or (visited[i][j] == 1) or (mat[i][j] != target[ind]):
				return
			if ind == len(target) - 1:
				ans[0] = ans[0] + 1
				return
			visited[i][j] = 1
			func(i + 1, j, ind + 1)
			func(i - 1, j, ind + 1)
			func(i, j - 1, ind + 1)
			func(i, j + 1, ind + 1)
			visited[i][j] = 0
		m = len(mat)
		n = len(mat[0])
		ans = [0]
		for i in range(m):
			for j in range(n):
				visited = [[0] * n for i in range(m)]
				if mat[i][j] == target[0]:
					func(i, j, 0)
		return ans[0]


class Solution:

	def solve(self, i, j, mat, target, index):
		n = len(mat)
		m = len(mat[0])
		length = len(target)
		count = 0
		if i >= 0 and j >= 0 and (i < n) and (j < m) and (target[index] == mat[i][j]):
			temp = mat[i][j]
			mat[i][j] = 0
			index = index + 1
			if index == length:
				count = 1
			else:
				count = count + self.solve(i - 1, j, mat, target, index)
				count = count + self.solve(i + 1, j, mat, target, index)
				count = count + self.solve(i, j - 1, mat, target, index)
				count = count + self.solve(i, j + 1, mat, target, index)
			mat[i][j] = temp
		return count

	def findOccurrence(self, mat, target):
		n = len(mat)
		m = len(mat[0])
		length = len(target)
		i = 0
		j = 0
		index = 0
		ans = 0
		for i in range(n):
			for j in range(m):
				ans = ans + self.solve(i, j, mat, target, index)
		return ans


class Solution:

	def dfs(self, i, j, mat, target, index, n, m, nn, visited):
		if index == nn:
			return 1
		visited[i][j] = True
		x = [-1, 0, 0, 1]
		y = [0, 1, -1, 0]
		ans = 0
		for t in range(4):
			tx = i + x[t]
			ty = j + y[t]
			if 0 <= tx < n and 0 <= ty < m and (mat[tx][ty] == target[index]) and (not visited[tx][ty]):
				ans += self.dfs(tx, ty, mat, target, index + 1, n, m, nn, visited)
		visited[i][j] = False
		return ans

	def findOccurrence(self, mat, target):
		n = len(mat)
		m = len(mat[0])
		ans = 0
		visited = [[False for _ in range(m)] for _ in range(n)]
		for i in range(n):
			for j in range(m):
				if mat[i][j] == target[0]:
					ans += self.dfs(i, j, mat, target, 1, n, m, len(target), visited)
		return ans


import sys
sys.setrecursionlimit(int(1000000.0))

class Solution:

	def findOccurrence(self, mat, target):
		dirx = [1, -1, 0, 0]
		diry = [0, 0, 1, -1]

		def isValid(x, y):
			if 0 <= x < len(mat) and 0 <= y < len(mat[0]) and (mat[x][y] != -1):
				return True
			return False

		def soln(s, x, y):
			if s == len(target):
				return 1
			res = 0
			for i in range(4):
				tempx = x + dirx[i]
				tempy = y + diry[i]
				if isValid(tempx, tempy):
					temp = mat[tempx][tempy]
					if temp == target[s]:
						mat[tempx][tempy] = -1
						res += soln(s + 1, tempx, tempy)
						mat[tempx][tempy] = temp
			return res
		res = 0
		for r in range(len(mat)):
			for c in range(len(mat[0])):
				temp = mat[r][c]
				if temp == target[0]:
					mat[r][c] = -1
					res += soln(1, r, c)
					mat[r][c] = temp
		return res


class Solution:

	def findOccurrence(self, mat, target):
		self.ans = 0
		(ROWS, COLS) = (len(mat), len(mat[0]))

		def dfs(r, c, i):
			if r >= ROWS or c >= COLS or r < 0 or (c < 0) or (mat[r][c] == '#'):
				return
			if i == len(target) - 1 and mat[r][c] == target[i]:
				self.ans += 1
				return
			if mat[r][c] != target[i]:
				return
			tmp = mat[r][c]
			mat[r][c] = '#'
			dfs(r + 1, c, i + 1)
			dfs(r, c + 1, i + 1)
			dfs(r, c - 1, i + 1)
			dfs(r - 1, c, i + 1)
			mat[r][c] = tmp
			return
		for i in range(ROWS):
			for j in range(COLS):
				dfs(i, j, 0)
		return self.ans


class Solution:

	def dfs(self, array, target, i, j, idx):
		count = 0
		if i >= 0 and j >= 0 and (i < len(array)) and (j < len(array[0])) and (array[i][j] == target[idx]):
			array[i][j] = '*'
			if idx == len(target) - 1:
				count = 1
			else:
				count += Solution().dfs(array, target, i + 1, j, idx + 1)
				count += Solution().dfs(array, target, i - 1, j, idx + 1)
				count += Solution().dfs(array, target, i, j + 1, idx + 1)
				count += Solution().dfs(array, target, i, j - 1, idx + 1)
			array[i][j] = target[idx]
		return count

	def findOccurrence(self, mat, target):
		occurences = 0
		n = len(mat)
		m = len(mat[0])
		for i in range(n):
			for j in range(m):
				occurences += Solution().dfs(mat, target, i, j, 0)
		return occurences


class Solution:

	def findOccurrence(self, mat, target):
		c = 0
		n = len(mat)
		m = len(mat[0])
		for i in range(n):
			for j in range(m):
				c += Solution().dfs(mat, target, i, j, 0)
		return c

	def dfs(self, arr, t, i, j, idx):
		count = 0
		if i >= 0 and j >= 0 and (i < len(arr)) and (j < len(arr[0])) and (arr[i][j] == t[idx]):
			arr[i][j] = '#'
			if idx == len(t) - 1:
				count = 1
			else:
				count += Solution().dfs(arr, t, i + 1, j, idx + 1)
				count += Solution().dfs(arr, t, i - 1, j, idx + 1)
				count += Solution().dfs(arr, t, i, j + 1, idx + 1)
				count += Solution().dfs(arr, t, i, j - 1, idx + 1)
			arr[i][j] = t[idx]
		return count


class Solution:

	def findOccurrence(self, mat, target):
		R = len(mat)
		C = len(mat[0])
		count = 0
		for r in range(R):
			for c in range(C):
				if mat[r][c] == target[0]:
					count += self.dfs(r, c, target, 0, mat)
		return count

	def dfs(self, r, c, target, i, mat):
		if not 0 <= r < len(mat) or not 0 <= c < len(mat[0]) or target[i] != mat[r][c] or (mat[r][c] == -1):
			return 0
		if i == len(target) - 1 and mat[r][c] == target[i]:
			return 1
		cc = 0
		nn = mat[r][c]
		mat[r][c] = -1
		cc += self.dfs(r + 1, c, target, i + 1, mat)
		cc += self.dfs(r, c + 1, target, i + 1, mat)
		cc += self.dfs(r - 1, c, target, i + 1, mat)
		cc += self.dfs(r, c - 1, target, i + 1, mat)
		mat[r][c] = nn
		return cc


class Node:

	def __init__(self, right, down, up, left):
		self.up = up
		self.down = down
		self.left = left
		self.right = right

class Solution:

	def findOccurrence(self, mat, target):

		def check(i, j):
			key = str(i) + '#' + str(j)
			if key in visited:
				return not visited[key]
			return 1

		def count(i, j, ind, dirr):
			key = str(i) + '#' + str(j) + '#' + str(ind)
			if ind < n and target[ind] != mat[i][j]:
				return 0
			if ind == n - 1:
				return 1
			if key in cache:
				if j + 1 < col and cache[key].right == 0:
					cache[key].right = count(i, j + 1, ind + 1, 3)
				if i + 1 < row and cache[key].down == 0:
					cache[key].down = count(i + 1, j, ind + 1, 2)
				if i - 1 >= 0 and cache[key].up == 0:
					cache[key].up = count(i - 1, j, ind + 1, 4)
				if j - 1 >= 0 and cache[key].left == 0:
					cache[key].left = count(i, j - 1, ind + 1, 1)
				if dirr == 1:
					return cache[key].down + cache[key].up + cache[key].left
				elif dirr == 2:
					return cache[key].right + cache[key].down + cache[key].left
				elif dirr == 3:
					return cache[key].right + cache[key].down + cache[key].up
				elif dirr == 4:
					return cache[key].right + cache[key].up + cache[key].left
			a = b = c = d = 0
			visited[str(i) + '#' + str(j)] = 1
			if j + 1 < col and check(i, j + 1):
				a = count(i, j + 1, ind + 1, 3)
			if i + 1 < row and check(i + 1, j):
				b = count(i + 1, j, ind + 1, 2)
			if i - 1 >= 0 and check(i - 1, j):
				c = count(i - 1, j, ind + 1, 4)
			if j - 1 >= 0 and check(i, j - 1):
				d = count(i, j - 1, ind + 1, 1)
			cache[key] = Node(a, b, c, d)
			visited[str(i) + '#' + str(j)] = 0
			if dirr == 0:
				return a + b + c + d
			elif dirr == 1:
				return b + c + d
			elif dirr == 2:
				return a + b + d
			elif dirr == 3:
				return a + b + c
			elif dirr == 4:
				return a + c + d
		n = len(target)
		(row, col) = (len(mat), len(mat[0]))
		visited = {}
		cache = {}
		ans = 0
		for i in range(0, row):
			for j in range(0, col):
				ans += count(i, j, 0, 0)
		return ans