Hello,
I am not sure if this is the right forum to ask, if so, please redirect me to the correct one.
I recently appeared for an online assesment for Crossover.
One of the questions was:
Given a 2D array of characters and a word, find out the total number of occurences of the word. A word may be formed in 8 directions.
I wrote the below code for it. It works fine if there are two separate occurences of the word. But if multiple occurences originate from the a single letter, it gets all messed up, as in it returns an absurdly high count.
Any help will be appreciated.
char[][] board = new char[][] { "ATT".toCharArray(),
"TXX".toCharArray(),
"TXX".toCharArray() };
System.out.println(wordCount(board, "ATT"));
private static final int[] dirX = { -1, -1, -1, 0, 0, 1, 1, 1 };
private static final int[] dirY = { -1, 0, 1, -1, 1, -1, 0, 1 };
static int wordCount(char[][] board, String word) {
int m = board.length, n = board[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0))
count += wordCountDfs(board, word, i, j, -1, -1, 0, 0);
}
}
return count;
}
static int wordCountDfs(char[][] board, String word, int row, int col, int prevRow, int prevCol, int count,int idx) {
if (col < 0 || col >= board.length || row < 0 || row >= board[0].length || (row == prevRow && col == prevCol) || idx > word.length() - 1 || board[row][col] != word.charAt(idx)) {
return 0;
}
System.out.println(board[row][col] + " " + row + ":" + col);
if (idx == word.length() - 1) {
count++;
}
for(int i = 0; i < 8; i++){
count += wordCountDfs(board, word, row + dirX[i], col + dirY[i], row, col, count, idx + 1);
}
return count;
}Comments (0)