Question Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
There is an optimization that you can make, which is to do the search only if you know that the board has enough letters to construct the word. If the board does not have enough letters, then there is no need to do the search.
It would be something like this:
```
public boolean exist(char[][] board, String word) {
There is an optimization that you can make, which is to do the search only if you know that the board has enough letters to construct the word. If the board does not have enough letters, then there is no need to do the search.
It would be something like this:
```
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) {
return false;
}
if (!hasEnoughLetters(board, word)) return false;
int rows = board.length;
int cols = board[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(board, i, j, word, 0)) {
return true;
}
}
}
return false;
}
private boolean hasEnoughLetters(char[][] board,String word) {
int[] freq = new int[128];
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[row].length; col++) {
freq[board[row][col]]++;
}
}
for (int index = 0; index < word.length; index++) {
freq[word.charAt(index)]--;
if (freq[word[index]] < 0) return false;
}
return true;
}
```
I agree, this is definitely a good case to check before doing any DFS traversal :)