[Geeks for Geeks] Count occurences of a given word in a 2-d array

Count occurences of a given word in a 2-d array

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.

  • Time : O(nm * |target|)
  • Space : O(|target|)
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
class Solution {
int res, n, m;
void floodfill(vector<vector<char>> &mat, string& t, int p, int y, int x) {
if(p == t.length()) res++;
else {
if(0 <= y and y < n and 0 <= x and x < m and mat[y][x] == t[p]) {
mat[y][x] = '#';

floodfill(mat, t, p + 1, y - 1, x);
floodfill(mat, t, p + 1, y + 1, x);
floodfill(mat, t, p + 1, y, x + 1);
floodfill(mat, t, p + 1, y, x - 1);

mat[y][x] = t[p];
}
}
}
public:
int findOccurrence(vector<vector<char>> &mat, string target) {
res = 0, n = mat.size(), m = mat[0].size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
floodfill(mat, target, 0, i, j);
}
}
return res / 4;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/19/PS/GeeksforGeeks/count-occurences-of-a-given-word-in-a-2-d-array/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.