Hard
Subtopics
array·backtracking·matrix·string·trie
Companies
airbnb·amazon·apple·bloomberg·bytedance·cisco·citadel·facebook·google·houzz·microsoft·oracle·roblox·salesforce·snapchat·uber·yahoo·zillowLast updated: Aug 4, 2025
Given an m x nboard of characters and a list of strings words, return all words on the board.
Each word must 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 in a word.
Boggle is a game played on a 4 x 4 grid of letters. The goal is to find as many words as possible that can be formed by a sequence of adjacent letters in the grid, using each cell at most once. Given a game board and a dictionary of valid words, implement a Boggle solver.
Key differences:
Movement: Boggle allows 8 directions (including diagonals), Word Search II uses 4 directions
Grid size: Boggle is traditionally 4x4, Word Search II can be any m×n
Word source: Boggle uses a dictionary, Word Search II uses a specific word list
Minimum length: Boggle typically requires 3+ character words
public List<String>findWords(char[][] board, String[] words) {
List<String> ans =new ArrayList<String> ();
int m = board.length;
int n = board[0].length;
for (String word: words) {
boolean flag =false;
for (int i = 0; i<m; i++) {
for (int j = 0; j<n; j++) {
char[][] newBoard =newchar[m][n];
for (int x = 0; x<m; x++) {
for (int y = 0; y<n; y++) {
newBoard[x][y]= board[x][y];
}
}
if (dfs(newBoard, word, i, j, 0)) {
flag =true;
}
}
}
if (flag) {
ans.add(word);
}
}
return ans;
}
publicbooleandfs(char[][] board, String word, int i, int j, int k) {
int m = board.length;
int n = board[0].length;
if (i<0 || j<0 || i >= m || j >= n || k > word.length() - 1) {
returnfalse;
}
if (board[i][j]== word.charAt(k)) {
char temp = board[i][j];
board[i][j]='#';
if (k == word.length() - 1) {
returntrue;
} elseif (dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i, j - 1, k + 1) || dfs(board, word, i, j + 1, k + 1)) {
board[i][j]= temp;
returntrue;
}
} else {
returnfalse;
}
returnfalse;
}