The Grid Search HackerRank Solution in C, C++, Java, Python

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() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    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)
    {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        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/

 

Leave a Comment