This is an iterative method for the recursive method that was previously explained. Here, we attempt to move iteratively 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.
- We carry out this action for each grid cell.
C++
// C++ program to search a word in a 2D grid
#include <bits/stdc++.h>
using namespace std;
// This function searches for the given word
// in all 8 directions from the coordinate.
bool search2D(vector<vector<char>> grid, int row, int col, string word) {
int m = grid.size();
int n = grid[0].size();
// return false if the given coordinate
// does not match with first index char.
if (grid[row][col] != word[0])
return false;
int len = word.size();
// 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 };
// This loop will search in all the 8 directions
// one by one. It will return true if one of the
// directions contain the word.
for (int dir = 0; dir < 8; dir++) {
// Initialize starting point for current direction
int k, currX = row + x[dir], currY = col + y[dir];
// First character is already checked, match remaining
// characters
for (k = 1; k < len; k++) {
// break if out of bounds
if (currX >= m || currX < 0 || currY >= n || currY < 0)
break;
if (grid[currX][currY] != word[k])
break;
// Moving in particular direction
currX += x[dir], currY += y[dir];
}
// If all character matched, then value of must
// be equal to length of word
if (k == len)
return true;
}
// if word is not found in any direction,
// then return false
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;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
// if the word is found from this coordinate,
// then append it to result.
if(search2D(grid, i, j, word)){
ans.push_back({i, j});
}
}
}
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 word in 2D
// grid in 8 directions
import java.util.*;
class GfG {
// This function searches for the given word
// in all 8 directions from the coordinate.
static boolean search2D(char[][] grid, int row, int col,String word) {
int m = grid.length;
int n = grid[0].length;
// return false if the given coordinate
// does not match with first index char.
if (grid[row][col] != word.charAt(0))
return false;
int len = word.length();
// 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 };
// This loop will search in all the 8 directions
for (int dir = 0; dir < 8; dir++) {
int k, currX = row + x[dir],
currY = col + y[dir];
// First character is already checked, match
// remaining
for (k = 1; k < len; k++) {
if (currX >= m || currX < 0 || currY >= n
|| currY < 0)
break;
if (grid[currX][currY] != word.charAt(k))
break;
currX += x[dir];
currY += y[dir];
}
if (k == len)
return true;
}
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;
// Max possible occurrences
int[][] ans = new int[m * n][2];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (search2D(grid, i, j, word)) {
ans[count][0] = i;
ans[count][1] = j;
count++;
}
}
}
// Resize the array to fit the actual number of
// found coordinates
int[][] result = new int[count][2];
for (int i = 0; i < count; i++) {
result[i] = ans[i];
}
return result;
}
static void printResult(int[][] ans) {
for (int[] coords : ans) {
System.out.print( "{" + coords[0] + "," + coords[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 word in 2D grid in 8 directions
# This function searches for the given word
# in all 8 directions from the coordinate.
def search2D(grid, row, col, word):
m = len(grid)
n = len(grid[0])
# return false if the given coordinate
# does not match with first index char.
if grid[row][col] != word[0]:
return False
lenWord = len(word)
# x and y are used to set the direction in which
# word needs to be searched.
x = [-1, -1, -1, 0, 0, 1, 1, 1]
y = [-1, 0, 1, -1, 1, -1, 0, 1]
# This loop will search in all the 8 directions
# one by one. It will return true if one of the
# directions contain the word.
for dir in range(8):
# Initialize starting point for current direction
currX, currY = row + x[dir], col + y[dir]
k = 1
while k < lenWord:
# break if out of bounds
if currX >= m or currX < 0 or currY >= n or currY < 0:
break
# break if characters dont match
if grid[currX][currY] != word[k]:
break
# Moving in particular direction
currX += x[dir]
currY += y[dir]
k += 1
# If all character matched, then value of must
# be equal to length of word
if k == lenWord:
return True
# if word is not found in any direction,
# then return false
return False
# This function calls search2D for each coordinate
def searchWord(grid, word):
m = len(grid)
n = len(grid[0])
ans = []
for i in range(m):
for j in range(n):
# if the word is found from this coordinate,
# then append it to result.
if search2D(grid, i, j, word):
ans.append((i, j))
return ans
def printResult(ans):
for coord in ans:
print(f"{{{coord[0]},{coord[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)JavaScript
// JavaScript program to search word in 2D grid in 8 directions
// This function searches for the given word
// in all 8 directions from the coordinate.
function search2D(grid, row, col, word) {
let m = grid.length;
let n = grid[0].length;
// return false if the given coordinate
// does not match with first index char.
if (grid[row][col] !== word[0]) return false;
let len = word.length;
// 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];
// This loop will search in all the 8 directions
// one by one. It will return true if one of the
// directions contain the word.
for (let dir = 0; dir < 8; dir++) {
// Initialize starting point for current direction
let currX = row + x[dir], currY = col + y[dir], k = 1;
// First character is already checked, match remaining
// characters
for (k = 1; k < len; k++) {
// break if out of bounds
if (currX >= m || currX < 0 || currY >= n || currY < 0) break;
// break if characters dont match
if (grid[currX][currY] !== word[k]) break;
// Moving in particular direction
currX += x[dir];
currY += y[dir];
}
// If all character matched, then value of must
// be equal to length of word
if (k === len) return true;
}
// if word is not found in any direction,
// then return false
return false;
}
// This function calls search2D for each coordinate
function searchWord(grid, word) {
let m = grid.length;
let n = grid[0].length;
let ans = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// if the word is found from this coordinate,
// then append it to result.
if (search2D(grid, i, j, word)) {
ans.push([i, j]);
}
}
}
return ans;
}
function printResult(ans) {
ans.forEach(coord => {
console.log("{" + coord[0] + "," + coord[1] + "}");;
});
}
let grid = [
['a', 'b', 'a', 'b'],
['a', 'b', 'e', 'b'],
['e', 'b', 'e', 'b']
];
let word = "abe";
let ans = searchWord(grid, word);
printResult(ans);