Problem name: Word Game
Topic: Depth First Search (DFS)
Tags: Depth First Search (DFS), Trie Nodes, Arrays, Hash Maps
Language used: Java
Difficulty Level: Hard
Problem Statement:
Your current project involves developing a word search game for children. The game
presents a grid of letters (single character only), and players must find words from a
predefined list within the grid. Words can be formed by connecting letters (single
character) that are adjacent horizontally or vertically.
Given a list of words and a grid of letters, you need to write a function that checks if
each word from the list can be found in the grid. Each letter in the grid can be used only
once per word, and words must be formed by sequentially adjacent letters (horizontally
or vertically).
Note: The function should return a list of 1s and 0s corresponding to whether each word
can be found in the grid.
Additionally, if the grid contains any string or number more than one digit and also
characters that are neither alphabet letters nor numbers, the function should return a list
with a single element: 0.
Input Format:
The first line of input contains a single integer n, representing the size of the grid
(n x n).
The next n lines contain n space-separated characters each, representing the
grid content row by row. The characters can be alphabets ('a' to 'z') or (‘A’ to ‘Z’)
or numbers ('0' to '9').
The next line contains a single integer m, representing the number of words
which user wants to add in the predefined list.
The next m lines contain one word each for which user wants to check the
presence in the n x n grid.
Output Format:
Display m space-separated integers (1s and 0s) where each integer indicates whether
the corresponding word from the list can be found in the grid. Additionally, if the grid
contains any special characters (characters that are neither alphabet letters nor
numbers), display a single integer: 0.
Constraints:
The grid maximum size can be 10x10.
The grid will contain only alphabet letters and numbers. If there are any
characters (like string or 2-digit, 3 digit number), the function should return [0].
The input matrix can only have numbers from 0-9 and alphabets from 'a-z' or ‘A –
Z’.
The length of each word will be at least 1 and at most 15.
Sample Input 1:
3
pig
fig
ned
3
pig
ned
to
Sample Output 1:
1
1
0
Explanation for Sample case 1:
Word "Pig":
We start at any cell that contains 'P'. The grid has 'p' in the top left corner (0, 0).
Check if "Pig" can be formed starting from 'p' (case insensitive, assuming here based on
output).
'P' -> (0, 0) 'i' -> (0, 1) 'g' -> (0, 2) - Found, output 1.
Word "Ned":
Start at any cell that contains 'N'. The grid has 'n' at (2, 0).
'N' -> (2, 0) 'e' -> (2, 1) 'd' -> (2, 2) - Found, output 1.
Word "To":
'T' is not present in the grid.
Not found, output 0.
Sample Input 2:
4
ANOL
AADP
CCMN
AASP
3
NOD
CAD
LPN
Sample Output 2:
1
1
1
Explanation for Sample case 2:
Word "NOD":
Start from any cell containing 'N'. The grid has 'N' at positions (0,1) and (2,3).
Starting from (0,1):
'N' -> (0,1)
'O' -> (0,2)
'D' -> (1,2)
The word "NOD" is found starting from (0,1). Therefore, the output for this word is 1.
Word "CAD":
Start from any cell containing 'C'. The grid has 'C' at positions (2,0) and (2,1).
Starting from (2,0):
'C' -> (2,0)
'A' -> (1,1)
'D' -> (1,2)
The word "CAD" is found starting from (2,0). Therefore, the output for this word is 1.
Word "LPN":
Start from any cell containing 'L'. The grid has 'L' at position (0,3).
Starting from (0,3):
'L' -> (0,3)
'P' -> (1,3)
'N' -> (2,3)
The word "LPN" is found starting from (0,3). Therefore, the output for this word is 1.
Code:
import [Link].*;
class WordSearch {
static class Node {
Map<Character, Node> child;
String word;
Node() {
child = new HashMap<>();
word = null;
}
}
public static List<Integer> wordGame(char[][] grid, String[] words) {
List<Integer> result = new ArrayList<>();
Node root = buildTrie(words);
for (String word : words) {
if (searchWord(grid, root, word)) {
[Link](1);
} else {
[Link](0);
}
}
return result;
}
public static boolean searchWord(char[][] board, Node root, String word) {
for (int i = 0; i < [Link]; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == [Link](0) && dfs(board, root, i, j, 0, word)) {
return true;
}
}
}
return false;
}
public static boolean dfs(char[][] board, Node curr, int i, int j, int index, String word) {
if (index == [Link]()) return true;
if (i < 0 || j < 0 || i >= [Link] || j >= board[0].length || board[i][j] !=
[Link](index) || [Link](board[i][j]) == null) {
return false;
}
char temp = board[i][j];
board[i][j] = '#';
boolean found = dfs(board, [Link](temp), i - 1, j, index + 1, word) ||
dfs(board, [Link](temp), i, j - 1, index + 1, word)
|| dfs(board, [Link](temp), i + 1, j, index + 1, word) || dfs(board,
[Link](temp), i, j + 1, index + 1, word);
board[i][j] = temp;
return found;
}
public static Node buildTrie(String[] words) {
Node root = new Node();
for (String word : words) {
Node curr = root;
for (char ch : [Link]()) {
if ( && ) {
// Special character found, return an empty trie
return new Node();
}
if () {
[Link](ch, new Node());
}
curr = [Link](ch);
}
[Link] = word;
}
return root;
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
int n = [Link]();
char[][] grid = new char[n][n];
// Input grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = [Link]().charAt(0);
}
}
int m = [Link]();
String[] words = new String[m];
// Input words
for (int i = 0; i < m; i++) {
words[i] = [Link]();
}
List<Integer> result = wordGame(grid, words);
for (int num : result) {
[Link](num);
}
}
}
One Compiler Link:
Word Game