Here we are going discuss about a 2D Grid or 2D array and check if a given word exists in Grid or not. Then we will write a C++ program to implement the same.
Given: A 2D Grid of character and a word to search for.
Problem: To check if the given word exists in the Grid or not.
Note: A word can be matched in 4 directions at any point, these directions are Horizontally Left and Right, Vertically Up and Down.
Example:
Word to search: cpp Input: grid[][] = {"axmy", "bcdf", "xppt", "raay"}; Output: Yes a c m y b g d f x p e t r a p s Input: grid[][] = {"acmy", "brdf", "xeet", "raps"}; Output : No
Solution: Below are steps to find the solution:
- Check every cell, if the cell has first character, then recur one by one and try all 4 directions from that cell for a match.
- Mark the position in the grid as visited and recur in the 4 possible directions.
- After recurring, again mark the position as unvisited.
- Once all the letters in the word is matched, return true.
Now let’s implement the same steps in C++ programming language:
C++ Program to check if word exists in Grid or not:
You can also execute this code on our online compiler.
#include <iostream> using namespace std; #define r 4 #define c 5 // Function to check if a word exists in a grid // x, y: current position in 2D array bool findmatch(char mat[r][c], string pat, int x, int y, int nrow, int ncol, int level) { int l = pat.length(); // Pattern matched if (level == l) return true; // Out of Boundary if (x < 0 || y < 0 || x >= nrow || y >= ncol) return false; // If grid matches with a letter while recursion if (mat[x][y] == pat[level]) { // Marking this cell as visited char temp = mat[x][y]; mat[x][y] = '#'; // finding subpattern in 4 directions bool res = findmatch(mat, pat, x - 1, y, nrow, ncol, level + 1) | findmatch(mat, pat, x + 1, y, nrow, ncol, level + 1) | findmatch(mat, pat, x, y - 1, nrow, ncol, level + 1) | findmatch(mat, pat, x, y + 1, nrow, ncol, level + 1); // marking this cell as unvisited again mat[x][y] = temp; return res; } else // Not matching then false return false; } // Function to check if the word exists in the grid or not bool checkMatch(char mat[r][c], string pat, int nrow, int ncol) { int l = pat.length(); // if total characters in matrix is less then pattern length if (l > nrow * ncol) return false; // Traverse in the grid for (int i = 0; i < nrow; i++) { for (int j = 0; j < ncol; j++) { // If first letter matches, then recur and check if (mat[i][j] == pat[0]) if (findmatch(mat, pat, i, j, nrow, ncol, 0)) return true; } } return false; } int main() { char grid[r][c] = { "axmy", "bcdf", "xppt", "raay" }; // Function to check if word exists or not if (checkMatch(grid, "cpp", r, c)) cout << "Yes"; else cout << "No"; return 0; }
OUTPUT:
Yes
Comment below in case if any issues or errors you are getting or to discuss more about the problem explained above.