Given a 2D grid of characters and a word/ multiple words, the task is to check if that word/words exist in the grid or not. A word can be matched in 4 directions at any point.
The 4 directions are Horizontally Left and Right, Vertically Up and Down.
Examples:
Input: grid[][] = {"axmy",
"bgdf",
"xeet",
"raks"};
Output: Yes
a x m y
b g d f
x e e t
r a k s
Input: grid[][] = {"axmy",
"brdf",
"xeet",
"rass"};
Output : No
Source: Microsoft Interview
Approach when a single word is to be checked : The idea used here is described in the steps below:
- Check every cell, if the cell has the 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 are matched, return true.
Below is the implementation of the above approach:
C++
// C++ program to check if the word// exists in the grid or not#include <bits/stdc++.h>using namespace std;#define r 4#define c 5// Function to check if a word exists in a grid// starting from the first match in the grid// level: index till which pattern is matched// x, y: current position in 2D arraybool findmatch(char mat[r], 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 notbool checkMatch(char mat[r], string pat, int nrow, int ncol){ int l = pat.length(); // if total characters in matrix is // less than 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;}// Driver Codeint main(){ char grid[r] = { "axmy", "bgdf", "xeet", "raks" }; // Function to check if word exists or not if (checkMatch(grid, "neveropen", r, c)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to check if the word// exists in the grid or notclass GFG{ static final int r = 4;static final int c = 4;// Function to check if a word exists in a grid// starting from the first match in the grid// level: index till which pattern is matched// x, y: current position in 2D arraystatic boolean findmatch(char mat[][], 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.charAt(level)) { // Marking this cell as visited char temp = mat[x][y]; mat[x][y] = '#'; // finding subpattern in 4 directions boolean 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 notstatic boolean checkMatch(char mat[][], String pat, int nrow, int ncol){ int l = pat.length(); // if total characters in matrix is // less than 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.charAt(0)) if (findmatch(mat, pat, i, j, nrow, ncol, 0)) return true; } } return false;}// Driver Codepublic static void main(String[] args){ char grid[][] = { "axmy".toCharArray(), "bgdf".toCharArray(), "xeet".toCharArray(), "raks".toCharArray() }; // Function to check if word exists or not if (checkMatch(grid, "neveropen", r, c)) System.out.print("Yes"); else System.out.print("No");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to check if the word # exists in the grid or not r = 4c = 4# Function to check if a word exists # in a grid starting from the first # match in the grid level: index till # which pattern is matched x, y: current # position in 2D array def findmatch(mat, pat, x, y, nrow, ncol, level) : l = len(pat) # Pattern matched if (level == l) : return True # Out of Boundary if (x < 0 or y < 0 or x >= nrow or y >= ncol) : return False # If grid matches with a letter # while recursion if (mat[x][y] == pat[level]) : # Marking this cell as visited temp = mat[x][y] mat[x].replace(mat[x][y], "#") # finding subpattern in 4 directions 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].replace(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 def checkMatch(mat, pat, nrow, ncol) : l = len(pat) # if total characters in matrix is # less than pattern length if (l > nrow * ncol) : return False # Traverse in the grid for i in range(nrow) : for j in range(ncol) : # 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# Driver Code if __name__ == "__main__" : grid = ["axmy", "bgdf", "xeet", "raks"] # Function to check if word # exists or not if (checkMatch(grid, "neveropen", r, c)) : print("Yes") else : print("No") # This code is contributed by Ryuga |
Javascript
<script> // JavaScript program to check if the word // exists in the grid or not let r = 4; let c = 4; // Function to check if a word exists in a grid // starting from the first match in the grid // level: index till which pattern is matched // x, y: current position in 2D array function findmatch(mat, pat, x, y, nrow, ncol, level) { let 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 let temp = mat[x][y]; mat[x][y] = '#'; // finding subpattern in 4 directions let 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 function checkMatch(mat, pat, nrow, ncol) { let l = pat.length; // if total characters in matrix is // less than pattern length if (l > nrow * ncol) return false; // Traverse in the grid for (let i = 0; i < nrow; i++) { for (let 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; } let grid = [ "axmy".split(''), "bgdf".split(''), "xeet".split(''), "raks".split('') ]; // Function to check if word exists or not if (checkMatch(grid, "neveropen", r, c)) document.write("Yes"); else document.write("No");</script> |
C#
// C# program to check if the word// exists in the grid or notusing System;class GFG{ static readonly int r = 4;static readonly int c = 4;// Function to check if a word exists in a grid// starting from the first match in the grid// level: index till which pattern is matched// x, y: current position in 2D arraystatic bool findmatch(char [,]mat, 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 notstatic bool checkMatch(char [,]mat, String pat, int nrow, int ncol){ int l = pat.Length; // if total characters in matrix is // less than 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;}// Driver Codepublic static void Main(String[] args){ char [,]grid = { {'a','x','m','y'}, {'b','g','d','f'}, {'x','e','e','t'}, {'r','a','k','s'} }; // Function to check if word exists or not if (checkMatch(grid, "neveropen", r, c)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by 29AjayKumar |
Output
Yes
Time Complexity: O(r*c), as we are using recursion to traverse the matrix. Where r and c are the rows and columns of the grid.
Auxiliary Space: O(r*c), as we are using extra space for the matrix. Where r and c are the rows and columns of the grid.
Approach when a group of words are to be checked : The idea used here is described in the steps below:
- iterate through group of words and check every cell, if the cell has the 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 are matched, return true, put it in answer list.
- return the answer list from a function and display
C++
#include <bits/stdc++.h>using namespace std;// making a solution class to solve the problem and to keep// the components and functions of solution togetherclass Solution {public: // making the possible moves in movers array // if 4 directions are to be checked vector<vector<int> > mover = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // if 8 directions are to be checked // vector<vector<int>>mover={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}}; // making the board global variable vector<vector<char> > board; // depth first search for the string, with the // coordinates and a visited array to take care that we // do not overlap the places visited already bool dfs(int x, int y, string& s, vector<vector<bool> > vis) { // if string length becomes 0 means string is found if (s.length() == 0) return true; vis[x][y] = true; // making a solution boolean to see if we can // perform depth search to find answer bool sol = false; // making possible moves for (int i = 0; i < mover.size(); i++) { int curr_x = mover[i][0] + x; int curr_y = mover[i][1] + y; // checking for out of bound areas if (curr_x >= 0 && curr_x < board.size()) { if (curr_y >= 0 && curr_y < board[0].size()) { // checking for similarity in the first // letter and the visited array if (board[curr_x][curr_y] == s[0] && vis[curr_x][curr_y] == false) { string k = s.substr( 1); // removing the first letter // from the string sol |= dfs(curr_x, curr_y, k, vis); } } } } return sol; } // making a function findwords to find words along with // their location which inputs the board and list of // words vector<string> findWords(vector<vector<char> >& board, vector<string>& words) { this->board = board; // making board a global variable vector<string> ans; vector<vector<bool> > vis( board.size(), vector<bool>(board[0].size(), false)); // visited array for (auto& word : words) { for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[i].size(); j++) { if (board[i][j] == word[0]) { // if first letter of(i,j)== // string's first letter then we can // perform dfs to check the // possibility of string being present // from location (i,j) string s = word.substr(1); if (dfs(i, j, s, vis)) { ans.push_back(word); break; } } } if (ans.size() && ans.back() == word) break; } } return ans; }};int main(){ // making 1 instance of class solution as solver Solution solver; vector<vector<char> > board = { { 'o', 'a', 'a', 'n' }, { 'e', 't', 'a', 'e' }, { 'i', 'h', 'k', 'r' }, { 'i', 'f', 'l', 'v' } }; vector<string> words = { "oath", "pea", "eat", "rain" }; // using the function findwords from our solution class // to find the answer vector<string> ans = solver.findWords(board, words); // printing the answer cout << "words present:\n"; for (auto& part : ans) cout << part << endl; return 0;}//contributed by Naman Anand |
Java
import java.util.*;class Solution { // Making the possible moves in movers array int[][] mover = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // Making the board global variable char[][] board; // Depth first search for the string, with the // coordinates and a visited array to take care that we // do not overlap the places visited already public boolean dfs(int x, int y, String s, boolean[][] vis) { // If string length becomes 0 means string is found if (s.length() == 0) { return true; } vis[x][y] = true; // Making a solution boolean to see if we can // perform depth search to find answer boolean sol = false; // Making possible moves for (int i = 0; i < mover.length; i++) { int curr_x = mover[i][0] + x; int curr_y = mover[i][1] + y; // Checking for out of bound areas if (curr_x >= 0 && curr_x < board.length) { if (curr_y >= 0 && curr_y < board[0].length) { // Checking for similarity in the first // letter and the visited array if (board[curr_x][curr_y] == s.charAt(0) && !vis[curr_x][curr_y]) { // Removing the first letter from the string String k = s.substring(1); sol |= dfs(curr_x, curr_y, k, vis); } } } } return sol; } // Making a function findWords to find words along with // their location which inputs the board and list of // words public List<String> findWords(char[][] board, String[] words) { this.board = board; List<String> ans = new ArrayList<>(); for (String word : words) { boolean[][] vis = new boolean[board.length][board[0].length]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) { if (board[i][j] == word.charAt(0)) { // If first letter of(i,j)== // string's first letter then we can // perform dfs to check the // possibility of string being present // from location (i,j) String s = word.substring(1); if (dfs(i, j, s, vis)) { ans.add(word); break; } } } if (!ans.isEmpty() && ans.get(ans.size() - 1).equals(word)) { break; } } } return ans; }}class Main { public static void main(String[] args) { // making 1 instance of class solution as solver Solution solver = new Solution(); char[][] board = { {'o','a','a','n'}, {'e','t','a','e'}, {'i','h','k','r'}, {'i','f','l','v'} }; String[] words = {"oath","pea","eat","rain"}; //Function call System.out.println("Words present: "); List<String> arr = solver.findWords(board, words); for (int i = 0; i < arr.size(); i++) { System.out.println(arr.get(i)); } }} |
Python3
class Solution: # making the possible moves in movers array # if 4 directions are to be checked mover = [ [1, 0], [0, 1], [-1, 0], [0, -1] ] # if 8 directions are to be checked # mover = [[1,0], [0,1], [-1,0], [0,-1], [1,1], [-1,-1], [1,-1], [-1,1]] # making the board global variable board = [] # depth first search for the string, with the # coordinates and a visited array to take care that we # do not overlap the places visited already def dfs(self, x, y, s, vis): # if string length becomes 0 means string is found if len(s) == 0: return True vis[x][y] = True # making a solution boolean to see if we can # perform depth search to find answer sol = False # making possible moves for i in range(len(self.mover)): curr_x = self.mover[i][0] + x curr_y = self.mover[i][1] + y # checking for out of bound areas if curr_x >= 0 and curr_x < len(self.board): if curr_y >= 0 and curr_y < len(self.board[0]): # checking for similarity in the first # letter and the visited array if self.board[curr_x][curr_y] == s[0] and vis[curr_x][curr_y] == False: # removing the first letter from the string k = s[1:] sol |= self.dfs(curr_x, curr_y, k, vis) return sol # making a function findwords to find words along with # their location which inputs the board and list of # words def findWords(self, board, words): self.board = board ans = [] for word in words: vis = [[False for _ in range(len(board[0]))] for _ in range(len(board))] for i in range(len(board)): for j in range(len(board[i])): if board[i][j] == word[0]: # if first letter of(i,j)== # string's first letter then we can # perform dfs to check the # possibility of string being present # from location (i,j) s = word[1:] if self.dfs(i, j, s, vis): ans.append(word) break if ans and ans[-1] == word: break return ans# making 1 instance of class solution as solversolver = Solution()board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ]words = ["oath","pea","eat","rain"]#Function callprint("Words present: ")arr=solver.findWords(board, words)for i in range(len(arr)): print(arr[i]) # This code is contributed by lokeshpotta20. |
Javascript
class Solution { // making the possible moves in movers array // if 4 directions are to be checked mover = [ [1, 0], [0, 1], [-1, 0], [0, -1] ]; // if 8 directions are to be checked // mover = [[1,0], [0,1], [-1,0], [0,-1], [1,1], [-1,-1], [1,-1], [-1,1]]; // making the board global variable board = []; // depth first search for the string, with the // coordinates and a visited array to take care that we // do not overlap the places visited already dfs(x, y, s, vis) { // if string length becomes 0 means string is found if (s.length === 0) { return true; } vis[x][y] = true; // making a solution boolean to see if we can // perform depth search to find answer let sol = false; // making possible moves for (let i = 0; i < this.mover.length; i++) { let curr_x = this.mover[i][0] + x; let curr_y = this.mover[i][1] + y; // checking for out of bound areas if (curr_x >= 0 && curr_x < this.board.length) { if (curr_y >= 0 && curr_y < this.board[0].length) { // checking for similarity in the first // letter and the visited array if (this.board[curr_x][curr_y] == s[0] && vis[curr_x][curr_y] == false) { // removing the first letter from the string let k = s.substring(1); sol |= this.dfs(curr_x, curr_y, k, vis); } } } } return sol; } // making a function findwords to find words along with // their location which inputs the board and list of // words findWords(board, words) { this.board = board; let ans = []; for (let word of words) { let vis = new Array(board.length).fill(false).map(() => new Array(board[0].length).fill(false)); for (let i = 0; i < board.length; i++) { for (let j = 0; j < board[i].length; j++) { if (board[i][j] == word[0]) { // if first letter of(i,j)== // string's first letter then we can // perform dfs to check the // possibility of string being present // from location (i,j) let s = word.substring(1); if (this.dfs(i, j, s, vis)) { ans.push(word); break; } } } if (ans.length && ans[ans.length - 1] == word) { break; } } } return ans; }}// making 1 instance of class solution as solverlet solver = new Solution();let board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v']];let words = ["oath","pea","eat","rain"];// Call the findWords method to search for wordsconst foundWords = solver.findWords(board, words);// Print the words that were foundconsole.log("Words present:");foundWords.forEach(word => console.log(word)); |
C#
// c# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class Solution { // Making the possible moves in moves array private static readonly int[][] Moves = { new[] {1, 0}, new[] {0, 1}, new[] {-1, 0}, new[] {0, -1} }; // Making the board global variable private char[][] _board; // Making a function findWords to find words along with // their location which inputs the board and list of // words public IList<string> FindWords(char[][] board, string[] words) { _board = board; var result = new List<string>(); foreach (var word in words) { if (Exists(word)) { result.Add(word); } } return result; } private bool Exists(string word) { for (var i = 0; i < _board.Length; i++) { for (var j = 0; j < _board[0].Length; j++) { if (_board[i][j] == word[0] && Search(word, i, j, 0)) { return true; } } } return false; } private bool Search(string word, int i, int j, int k) { if (k == word.Length) { return true; } if (i < 0 || j < 0 || i == _board.Length || j == _board[0].Length) { return false; } if (_board[i][j] != word[k]) { return false; } var temp = _board[i][j]; _board[i][j] = '#'; foreach (var move in Moves) { if (Search(word, i + move[0], j + move[1], k + 1)) { _board[i][j] = temp; return true; } } _board[i][j] = temp; return false; }}// Driver Codepublic class Program { public static void Main() { // making 1 instance of class solution as solver var solver = new Solution(); var board = new char[][] { new char[] {'o', 'a', 'a', 'n'}, new char[] {'e', 't', 'a', 'e'}, new char[] {'i', 'h', 'k', 'r'}, new char[] {'i', 'f', 'l', 'v'} }; var words = new string[] {"oath", "pea", "eat", "rain"}; var ans = solver.FindWords(board, words); Console.WriteLine("Words present:"); foreach (var word in ans) { Console.WriteLine(word); } }}// This code is contributed by Prince Kumar |
Output
words present: oath eat
Time Complexity: O(r*c*len(words)*number of words), as we are using recursion to traverse the matrix. Where r and c are the rows and columns of the grid.
Auxiliary Space: O(r*c*number of words), as we are using extra space for the matrix. Where r and c are the rows and columns of the grid.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
