Given a 2D grid of characters and a word, find all occurrences of given word in grid. A word can be matched in all 8 directions at any point. Word is said be found in a direction if all characters match in this direction (not in zig-zag form).
The 8 directions are, Horizontally Left, Horizontally Right, Vertically Up and 4 Diagonal directions.
Example:
Input: grid[][] = {"GEEKSFORGEEKS",
"GEEKSQUIZGEEK",
"IDEQAPRACTICE"};
word = "GEEKS"
Output: pattern found at 0, 0
pattern found at 0, 8
pattern found at 1, 0
Input: grid[][] = {"GEEKSFORGEEKS",
"GEEKSQUIZGEEK",
"IDEQAPRACTICE"};
word = "EEE"
Output: pattern found at 0, 2
pattern found at 0, 10
pattern found at 2, 2
pattern found at 2, 12
Below diagram shows a bigger grid and presence of different words in it.
Source: Microsoft Interview Question
The idea used here is simple, we check every cell. If cell has first character, then we one by one try all 8 directions from that cell for a match. Implementation is interesting though. We use two arrays x[] and y[] to find next move in all 8 directions.
Below are implementation of the same.
C++
// C++ programs to search a word in a 2D grid #include<bits/stdc++.h> using namespace std; // Rows and columns in given grid #define R 3 #define C 14 // For searching in all 8 direction int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int y[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; // This function searches in all 8-direction from point // (row, col) in grid[][] bool search2D(char grid[R][C], int row, int col, string word) { // If first character of word doesn't match with // given starting point in grid. if (grid[row][col] != word[0]) return false; int len = word.length(); // Search word in all 8 directions starting from (row,col) for (int dir = 0; dir < 8; dir++) { // Initialize starting point for current direction int k, rd = row + x[dir], cd = col + y[dir]; // First character is already checked, match remaining // characters for (k = 1; k < len; k++) { // If out of bound break if (rd >= R || rd < 0 || cd >= C || cd < 0) break; // If not matched, break if (grid[rd][cd] != word[k]) break; // Moving in particular direction rd += x[dir], cd += y[dir]; } // If all character matched, then value of must // be equal to length of word if (k == len) return true; } return false; } // Searches given word in a given matrix in all 8 directions void patternSearch(char grid[R][C], string word) { // Consider every point as starting point and search // given word for (int row = 0; row < R; row++) for (int col = 0; col < C; col++) if (search2D(grid, row, col, word)) cout << "pattern found at " << row << ", " << col << endl; } // Driver program int main() { char grid[R][C] = {"GEEKSFORGEEKS", "GEEKSQUIZGEEK", "IDEQAPRACTICE" }; patternSearch(grid, "GEEKS"); cout << endl; patternSearch(grid, "EEE"); return 0; } |
Java
// Java program to search a word in a 2D grid import java.io.*; import java.util.*; class GFG { // Rows and columns in given grid static int R, C; // For searching in all 8 direction static int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 }; static int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 }; // This function searches in all 8-direction from point // (row, col) in grid[][] static boolean search2D(char[][] grid, int row, int col, String word) { // If first character of word doesn't match with // given starting point in grid. if (grid[row][col] != word.charAt(0)) return false; int len = word.length(); // Search word in all 8 directions // starting from (row,col) for (int dir = 0; dir < 8; dir++) { // Initialize starting point // for current direction int k, rd = row + x[dir], cd = col + y[dir]; // First character is already checked, // match remaining characters for (k = 1; k < len; k++) { // If out of bound break if (rd >= R || rd < 0 || cd >= C || cd < 0) break; // If not matched, break if (grid[rd][cd] != word.charAt(k)) break; // Moving in particular direction rd += x[dir]; cd += y[dir]; } // If all character matched, then value of must // be equal to length of word if (k == len) return true; } return false; } // Searches given word in a given // matrix in all 8 directions static void patternSearch(char[][] grid, String word) { // Consider every point as starting // point and search given word for (int row = 0; row < R; row++) { for (int col = 0; col < C; col++) { if (search2D(grid, row, col, word)) System.out.println("pattern found at " + row + ", " + col); } } } // Driver code public static void main(String args[]) { R = 3; C = 13; char[][] grid = {{'G','E','E','K','S','F','O','R','G','E','E','K','S'}, {'G','E','E','K','S','Q','U','I','Z','G','E','E','K'}, {'I','D','E','Q','A','P','R','A','C','T','I','C','E'}}; patternSearch(grid, "GEEKS"); System.out.println(); patternSearch(grid, "EEE"); } } // This code is contributed by rachana soma |
Output:
pattern found at 0, 0 pattern found at 0, 8 pattern found at 1, 0 pattern found at 0, 2 pattern found at 0, 10 pattern found at 2, 2 pattern found at 2, 12
Exercise: The above solution only print locations of word. Extend it to print the direction where word is present.
See this for solution of exercise.
leave a comment
0 Comments