forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
CountOccurencesOfAGivenWordInA2DArray.java
49 lines (45 loc) · 1.41 KB
/
CountOccurencesOfAGivenWordInA2DArray.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*https://practice.geeksforgeeks.org/problems/count-occurences-of-a-given-word-in-a-2-d-array/1/*/
class Solution
{
int count, m, n;
boolean[][] visited;
int[][] pos = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
public int findOccurrence(char mat[][], String target)
{
// Write your code here
count = 0;
m = mat.length;
n = mat[0].length;
visited = new boolean[m][n];
char[] arr = target.toCharArray();
int i, j;
for (i = 0; i < m; ++i)
for (j = 0; j < n; ++j)
count += dfs(mat, arr, i, j, 0);
return count;
}
private int dfs(char[][] mat, char[] str, int row, int col, int index)
{
int result = 0;
if (row >= 0 && row < m && col >= 0 && col < n && !visited[row][col] && mat[row][col] == str[index])
{
visited[row][col] = true;
int i, r, c;
if (index == str.length-1) result = 1;
else
{
if (mat[row][col] == str[index])
{
for (i = 0; i < 4; ++i)
{
r = row+pos[i][0];
c = col+pos[i][1];
result += dfs(mat, str, r, c, index+1);
}
}
}
visited[row][col] = false;
}
return result;
}
}