Given an array of strings of digits, try to find the occurrence of a given pattern of digits. In the grid and pattern arrays, each string represents a row in the grid. For example, consider the following grid:
1234567890 0987654321 1111111111 1111111111 2222222222
The pattern array is:
876543 111111 111111
The pattern begins at the second row and the third column of the grid and continues in the following two rows. The pattern is said to be present in the grid. The return value should be YES or NO, depending on whether the pattern is found. In this case, return YES.
Function Description
Complete the gridSearch function in the editor below. It should return YES if the pattern exists in the grid, or NO otherwise.
gridSearch has the following parameter(s):
string G[R]: the grid to search
string P[r]: the pattern to search for
Input Format
The first line contains an integer t, the number of test cases.
Each of the t test cases is represented as follows:
The first line contains two space-separated integers R and C, the number of rows in the search grid G and the length of each row string.
This is followed by R lines, each with a string of C digits that represent the grid G.
The following line contains two space-separated integers,r and c, the number of rows in the pattern grid P and the length of each pattern row string.
This is followed by r lines, each with a string of c digits that represent the pattern grid .
Returns
string: either YES or NO
Sample Input
2 10 10 7283455864 6731158619 8988242643 3830589324 2229505813 5633845374 6473530293 7053106601 0834282956 4607924137 3 4 9505 3845 3530 15 15 400453592126560 114213133098692 474386082879648 522356951189169 887109450487496 252802633388782 502771484966748 075975207693780 511799789562806 404007454272504 549043809916080 962410809534811 445893523733475 768705303214174 650629270887160 2 2 99 99
Sample Output
YES NO
Explanation
The first test in the input file is:
10 10 7283455864 6731158619 8988242643 3830589324 2229505813 5633845374 6473530293 7053106601 0834282956 4607924137 3 4 9505 3845 3530
The pattern is present in the larger grid as marked in bold below.
7283455864 6731158619 8988242643 3830589324 2229505813 5633845374 6473530293 7053106601 0834282956 4607924137
The second test in the input file is:
15 15 400453592126560 114213133098692 474386082879648 522356951189169 887109450487496 252802633388782 502771484966748 075975207693780 511799789562806 404007454272504 549043809916080 962410809534811 445893523733475 768705303214174 650629270887160 2 2 99 99
The search pattern is:
99 99
This pattern is not found in the larger grid.
The Grid Search HackerRank Solution in C
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int T, R,C,r,c,i,j,o1,o2;
char c1;
char* d1 = NULL;
char* d2 = NULL;
char* p1 = NULL;
char* p2 = NULL;
scanf("%d\n", &T);
while (T-- > 0)
{
scanf("%d %d\n", &R, &C);
p1 = d1 = (char*) malloc(R*C);
for (j=0; j<R; j++)
{
for (i=0; i<C; i++)
{
*p1++ = fgetc(stdin);
}
scanf("\n");
}
scanf("%d %d\n", &r, &c);
p2 = d2 = (char*) malloc(r*c);
for (j=0; j<r; j++)
{
for (i=0; i<c; i++)
{
*p2++ = fgetc(stdin);
}
scanf("\n");
}
for (o2=0; o2<=R-r; o2++)
{
for (o1=0; o1<=C-c; o1++)
{
p1 = &(d1[o2*C+o1]);
p2 = d2;
if (*p2 != *p1) continue;
for (j=0; j<r; j++)
{
for (i=0; i<c; i++)
{
if (*p2++ != *p1++) break;
}
p1 += C-c;
if (i<c) break;
}
if (j<r) continue;
else break;
}
if (o1<=C-c) break;
}
free(d2); d2 = NULL;
free(d1); d1 = NULL;
printf((o2 <= R-r)? "YES\n":"NO\n");
}
return 0;
}
The Grid Search HackerRank Solution in C++
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int T, R, C, r, c;
char G[1005][1005], P[1005][1005];
void solve() {
scanf("%d%d", &R, &C);
for (int i = 0; i < R; ++i) scanf("%s", G[i]);
scanf("%d%d", &r, &c);
for (int i = 0; i < r; ++i) scanf("%s", P[i]);
for (int i = 0; i <= R - r; ++i) {
for (int j = 0; j <= C - c; ++j) {
for (int a = 0; a < r; ++a) {
for (int b = 0; b < c; ++b) {
if (G[i+a][j+b] != P[a][b])
goto label1;
}
}
printf("YES\n");
return;
label1:;
}
}
printf("NO\n");
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}
The Grid Search HackerRank Solution in Java
import java.util.Scanner;
class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
nextCase:
for(int t = 0; t < T; t++) {
int R = in.nextInt();
int C = in.nextInt();
int[][] map = new int[R][C];
for(int i = 0; i < R; i++) {
String line = in.next();
for(int j = 0; j < C; j++) {
map[i][j] = line.charAt(j) - '0';
}
}
int r = in.nextInt();
int c = in.nextInt();
int[][] sub = new int[r][c];
for(int i = 0; i < r; i++) {
String line = in.next();
for(int j = 0; j < c; j++) {
sub[i][j] = line.charAt(j) - '0';
}
}
for(int i = 0; i <= R - r; i++) {
for(int j = 0; j <= C - c; j++) {
boolean works = true;
outer:
for(int a = 0; a < r; a++) {
for(int b = 0; b < c; b++) {
if(map[i + a][j + b] != sub[a][b]) {
works = false;
break outer;
}
}
}
if(works) {
System.out.println("YES");
continue nextCase;
}
}
}
System.out.println("NO");
}
}
}
The Grid Search HackerRank Solution in Python
# Enter your code here. Read input from STDIN. Print output to STDOUT
def find_all(string, substring):
index = []
L = len(string)
l = len(substring)
for i in xrange(L-l+1):
if string[i:i+l] == substring:
index.append(i)
return index
def find_pattern(grid, pattern):
R, C = len(grid), len(grid[0])
r, c = len(pattern), len(pattern[0])
for i in xrange(R-r+1):
indeces = find_all(grid[i], pattern[0])
if indeces:
for idx in indeces:
for j in xrange(i+1, i+r):
if pattern[j-i] != grid[j][idx:idx+c]:
break
else:
print 'YES'
return
print 'NO'
return
def main():
T = input()
for i in xrange(T):
R, C = map(int, raw_input().strip().split())
N = R * C
grid = []
for k in xrange(R):
grid.append(raw_input().strip())
r, c = map(int, raw_input().strip().split())
pattern = []
for k in xrange(r):
pattern.append(raw_input().strip())
find_pattern(grid, pattern)
if __name__ == '__main__':
main()
The Grid Search HackerRank Solution in C#
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
static void Main(String[] args)
{
int tests = Convert.ToInt32(Console.ReadLine());
for (int t = 0; t < tests; t++)
{
List<string> grid = new List<string>();
List<string> pattern = new List<string>();
bool contains = false;
string[] rc = Console.ReadLine().Split();
int rows = Convert.ToInt32(rc[0]);
int columns = Convert.ToInt32(rc[1]);
for (int r = 0; r < rows; r++)
{
grid.Add(Console.ReadLine());
}
string[] prc = Console.ReadLine().Split();
int prows = Convert.ToInt32(prc[0]);
int pcolumns = Convert.ToInt32(prc[1]);
for (int r = 0; r < prows; r++)
{
pattern.Add(Console.ReadLine());
}
for (int i = 0; i < grid.Count; i++)
{
if(grid[i].Contains(pattern[0]))
{
for (int j = 1; j < pattern.Count; j++)
{
if(!grid[i+j].Contains(pattern[j]))
{
break;
}
if (j == pattern.Count - 1)
{
contains = true;
}
}
}
}
if (contains)
Console.Out.WriteLine("YES");
else
Console.Out.WriteLine("NO");
}
}
}
Attempt The Grid Search HackerRank Solution
Link — https://www.hackerrank.com/challenges/the-grid-search/
Next HackerRank Challenge Solution
Link – https://exploringbits.com/happy-ladybugs-hackerrank-solution/
Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.