Finding every instance of a given word in a 2D grid with m*n characters is the work at hand. At any given time, a word can be matched in all eight directions. If every character in a word matches in that direction (not in zigzag form), the word is considered to be found in that direction.
Horizontally left, horizontally right, vertically up, vertically down, and four diagonal directions are the eight directions.
Note: The lexicographically smallest list should be the one that returns. The coordinates should only appear once in the list if the word may be discovered in several directions beginning from the same coordinates.
For instance:
Table of Content
- [Naive Approach] Using Recursion – O(m*n*k) Time and O(k) Space
- [Expected Approach] Using Iteration – O(m*n*k) Time and O(1) Space
Using Recursion – O(m*n*k) Time and O(k) Space
To locate the word, travel to each grid cell and look in all eight directions (up, down, left, right, and diagonals). We also attempt to travel in a single direction for every cell.
- As we proceed in the selected direction, we continuously verify whether the letter in the grid cell corresponds to the word.
- We save the beginning point if we locate the entire term.
- This is done recursively for each grid cell.
C++
// C++ program to search a word in a 2D grid
#include <bits/stdc++.h>
using namespace std;
// This function checks if the given
// coordinate is valid
bool validCoord(int x, int y, int m, int n) {
if (x>=0 && x<m && y>=0 && y<n)
return true;
return false;
}
// This function searches for the given word
// in a given direction from the coordinate.
bool findWord(int index, string word, vector<vector<char>> &grid,
int x, int y, int dirX, int dirY) {
// if word has been found
if (index == word.length()) return true;
// if the current coordinate is
// valid and characters match, then
// check the next index
if (validCoord(x, y, grid.size(), grid[0].size())
&& word[index] == grid[x][y])
return findWord(index+1, word, grid, x+dirX,
y+dirY, dirX, dirY);
return false;
}
// This function calls search2D for each coordinate
vector<vector<int>>searchWord(vector<vector<char>>grid,
string word){
int m = grid.size();
int n = grid[0].size();
vector<vector<int>>ans;
// x and y are used to set the direction in which
// word needs to be searched.
vector<int>x = { -1, -1, -1, 0, 0, 1, 1, 1 };
vector<int>y = { -1, 0, 1, -1, 1, -1, 0, 1 };
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
// Search in all 8 directions
for (int k=0; k<8; k++) {
// If word is found, then append the
// coordinates into answer and break.
if (findWord(0, word, grid, i, j, x[k], y[k])) {
ans.push_back({i,j});
break;
}
}
}
}
return ans;
}
void printResult(vector<vector<int>> ans) {
for (int i=0; i<ans.size(); i++) {
cout << "{" << ans[i][0] << "," << ans[i][1] << "}" << " ";
}
cout<<endl;
}
int main() {
vector<vector<char>> grid = {{'a','b','a','b'},
{'a','b','e','b'},
{'e','b','e','b'}};
string word = "abe";
vector<vector<int>> ans = searchWord(grid, word);
printResult(ans);
}
Java
// Java program to search a word in a 2D grid
import java.util.*;
class GfG {
// This function checks if the given
// coordinate is valid
static boolean validCoord(int x, int y, int m, int n) {
if (x >= 0 && x < m && y >= 0 && y < n)
return true;
return false;
}
// This function searches for the given word
// in a given direction from the coordinate.
static boolean findWord(int index, String word, char[][] grid,
int x, int y, int dirX, int dirY) {
// if word has been found
if (index == word.length()) return true;
// if the current coordinate is
// valid and characters match, then
// check the next index
if (validCoord(x, y, grid.length, grid[0].length) &&
word.charAt(index) == grid[x][y])
return findWord(index + 1, word, grid,
x + dirX, y + dirY, dirX, dirY);
return false;
}
// This function calls search2D for each coordinate
static int[][] searchWord(char[][] grid, String word) {
int m = grid.length;
int n = grid[0].length;
List<int[]> ans = new ArrayList<>();
// x and y are used to set the direction in which
// word needs to be searched.
int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 };
int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 };
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Search in all 8 directions
for (int k = 0; k < 8; k++) {
// If word is found, then append the
// coordinates into answer and break.
if (findWord(0, word, grid, i, j, x[k], y[k])) {
ans.add(new int[] { i, j });
break;
}
}
}
}
return ans.toArray(new int[0][]);
}
static void printResult(int[][] ans) {
for (int[] a : ans) {
System.out.print( "{" + a[0] + "," + a[1] + "}" + " ");
}
System.out.println();
}
public static void main(String[] args) {
char[][] grid = { { 'a', 'b', 'a', 'b' },
{ 'a', 'b', 'e', 'b' },
{ 'e', 'b', 'e', 'b' } };
String word = "abe";
int[][] ans = searchWord(grid, word);
printResult(ans);
}
}Python
# Python program to search a word in a 2D grid
# This function checks if the given
# coordinate is valid
def isValid(x, y, sizeX, sizeY):
return 0 <= x < sizeX and 0 <= y < sizeY
def findWordInDirection(grid, n, m, word, index,
x, y, dirX, dirY):
if index == len(word):
return True
if isValid(x, y, n, m) and word[index] == grid[x][y]:
return findWordInDirection(grid, n, m, word, index + 1,
x + dirX, y + dirY, dirX, dirY)
return False
def searchWord(grid, word):
ans = []
n = len(grid)
m = len(grid[0])
# Directions for 8 possible movements
directions = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
for i in range(n):
for j in range(m):
# Check if the first character matches
if grid[i][j] == word[0]:
for dirX, dirY in directions:
if findWordInDirection(grid, n, m, word, 0,
i, j, dirX, dirY):
ans.append([i, j])
break
return ans
def printResult(ans):
for a in ans:
print(f"{{{a[0]},{a[1]}}}", end=" ")
print()
if __name__ == "__main__":
grid = [['a', 'b', 'a', 'b'],
['a', 'b', 'e', 'b'],
['e', 'b', 'e', 'b']]
word = "abe"
ans = searchWord(grid, word)
printResult(ans)C#
// C# program to search a word in a 2D grid
using System;
using System.Collections.Generic;
class GfG {
// This function checks if the given
// coordinate is valid
static bool validCoord(int x, int y, int m, int n) {
if (x >= 0 && x < m && y >= 0 && y < n)
return true;
return false;
}
// This function searches for the given word
// in a given direction from the coordinate.
static bool findWord(int index, string word, char[,] grid,
int x, int y, int dirX, int dirY) {
// if word has been found
if (index == word.Length) return true;
// if the current coordinate is
// valid and characters match, then
// check the next index
if (validCoord(x, y, grid.GetLength(0), grid.GetLength(1))
&& word[index] == grid[x, y])
return findWord(index + 1, word, grid,
x + dirX, y + dirY, dirX, dirY);
return false;
}
// This function calls search2D for each coordinate
static int[][] searchWord(char[,] grid, string word) {
int m = grid.GetLength(0);
int n = grid.GetLength(1);
List<int[]> ans = new List<int[]>();
// x and y are used to set the direction in which
// word needs to be searched.
int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 };
int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 };
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Search in all 8 directions
for (int k = 0; k < 8; k++) {
// If word is found, then append the
// coordinates into answer and break.
if (findWord(0, word, grid, i, j, x[k], y[k])) {
ans.Add(new int[] { i, j });
break;
}
}
}
}
return ans.ToArray();
}
static void printResult(int[][] ans) {
foreach (var a in ans) {
Console.Write( "{" + a[0] + "," + a[1] + "}" + " ");
}
Console.WriteLine();
}
static void Main() {
char[,] grid = {
{ 'a', 'b', 'a', 'b' },
{ 'a', 'b', 'e', 'b' },
{ 'e', 'b', 'e', 'b' }
};
string word = "abe";
int[][] ans = searchWord(grid, word);
printResult(ans);
}
}JavaScript
// JavaScript program to search a word in a 2D grid
// This function checks if the given
// coordinate is valid
function validCoord(x, y, m, n) {
return (x >= 0 && x < m && y >= 0 && y < n);
}
// This function searches for the given word
// in a given direction from the coordinate.
function findWord(index, word, grid, x, y, dirX, dirY) {
// if word has been found
if (index === word.length) return true;
// if the current coordinate is
// valid and characters match, then
// check the next index
if (validCoord(x, y, grid.length, grid[0].length)
&& word[index] === grid[x][y])
return findWord(index + 1, word, grid, x + dirX, y + dirY, dirX, dirY);
return false;
}
// This function calls search2D for each coordinate
function searchWord(grid, word) {
let m = grid.length;
let n = grid[0].length;
let ans = [];
// x and y are used to set the direction in which
// word needs to be searched.
let x = [-1, -1, -1, 0, 0, 1, 1, 1];
let y = [-1, 0, 1, -1, 1, -1, 0, 1];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// Search in all 8 directions
for (let k = 0; k < 8; k++) {
// If word is found, then append the
// coordinates into answer and break.
if (findWord(0, word, grid, i, j, x[k], y[k])) {
ans.push([i, j]);
break;
}
}
}
}
return ans;
}
function printResult(ans) {
for (let i = 0; i < ans.length; i++) {
console.log("{" + ans[i][0] + "," + ans[i][1] + "}");
}
}
const grid = [
['a', 'b', 'a', 'b'],
['a', 'b', 'e', 'b'],
['e', 'b', 'e', 'b']
];
const word = "abe";
const ans = searchWord(grid, word);
printResult(ans);Output
{0,0} {0,2} {1,0}
Time Complexity: O(m*n*k), where m is the number of rows, n is the number of columns and k is the length of word.
Auxiliary Space: O(k), recursion stack space.