You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Hackerrank The Grid Search Solution

Hackerrank The Grid Search Solution

Beeze Aal
Beeze Aal

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Given a 2D array of digits or grid, try to find the occurrence of a given 2D pattern of digits. For example, consider the following grid:  1234567890 0987654321 1111111111 1111111111 2222222222

Assume we need to look for the following 2D pattern array:  876543 111111 111111

The 2D pattern begins at the second row and the third column of the grid.  The pattern is said to be present in the grid.

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):

  • G: the grid to search, an array of strings
  • P: the pattern to search for, an array of strings

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The first line contains an integer , the number of test cases.

Each of the  test cases is represented as follows:
The first line contains two space-separated integers  and , indicating the number of rows and columns in the grid .
This is followed by  lines, each with a string of  digits representing the grid .
The following line contains two space-separated integers,  and , indicating the number of rows and columns in the pattern grid .
This is followed by  lines, each with a string of  digits representing the pattern .

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}




Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Display YES or NO, depending on whether  is present in .

Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

YES
NO

Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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

As one may see, the given 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 cannot be found in the larger grid.

Solution in java8

Approach 1.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int R = in.nextInt();
            int C = in.nextInt();
            String[] G = new String[R];
            for(int G_i=0; G_i < R; G_i++){
                G[G_i] = in.next();
            }
            int r = in.nextInt();
            int c = in.nextInt();
            String[] P = new String[r];
            for(int P_i=0; P_i < r; P_i++){
                P[P_i] = in.next();
            }
            
            boolean found = true;
            int pi, index = 0, offset = 0;
            for(int i=0; i < G.length; ){
                //System.out.println(i);
                index = G[i].substring(offset).indexOf(P[0]);
                if(index == -1){
                    i++;
                    offset = 0;
                    continue;
                }
                pi = 1;
                found = true;
                for(int j=i+1; j < G.length && pi < P.length; j++){
                    if(G[j].substring(offset+index).indexOf(P[pi++]) != 0){
                        found = false;
                        offset++;
                        break;
                    }
                }
                if(found)
                    break;
            }
            if(found){
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

Approach 2.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int R = in.nextInt();
            int C = in.nextInt();
            String[] G = new String[R];
            for(int G_i=0; G_i < R; G_i++){
                G[G_i] = in.next();
            }
            int r = in.nextInt();
            int c = in.nextInt();
            String[] P = new String[r];
            for(int P_i=0; P_i < r; P_i++){
                P[P_i] = in.next();
            }

            boolean isTrue = false;
            for(int i=0;i<R-r+1;i++){
                for(int j=0;j<C-c+1;j++){
                    String as = G[i].substring(j,j+c);
                    if(as.contentEquals(P[0])){
                        int z = i+1;
                        for(int k=1;k<r;k++){
                            isTrue = true;
                            String at = G[z].substring(j,j+c);
                            if(!at.contentEquals(P[k])){
                                isTrue=false;
                                break;
                            }
                            z++;
                        }
                        if(isTrue){
                            break;
                        }
                    }
                    if(isTrue){
                        break;
                    }
                }
                if(isTrue){
                    break;
                }
            }
            System.out.println(isTrue?"YES":"NO");
        }
    }
}

Approach 3.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int R = in.nextInt();
            int C = in.nextInt();
            String[] G = new String[R];
            for(int G_i=0; G_i < R; G_i++){
                G[G_i] = in.next();
            }
            int r = in.nextInt();
            int c = in.nextInt();
            String[] P = new String[r];
            for(int P_i=0; P_i < r; P_i++){
                P[P_i] = in.next();
            }
            boolean hit = false;
            boolean stopLoop = false;
            for (int i = 0; i < R; i++){
                if (stopLoop){
                    break;
                }
                int firstIndex = G[i].indexOf(P[0]);
                while (firstIndex >= 0){
                    int counter = 1;
                    for (int j = 1; j < r; j++){
                        if ( j + i < R){
                            int nextIndex = G[i+j].indexOf(P[j]);
                            boolean partialHit = false;
                            while(nextIndex >= 0){
	                            if (nextIndex == firstIndex){
	                                partialHit = true;
	                            }
	                            nextIndex = G[i+j].indexOf(P[j], nextIndex+1);
                            }
                            if (!partialHit){
                                break;
                            } else {
                                counter++;
                            }
                        }
                    }
                    if (counter == r){
                        hit = true;
                    }
                    if (hit == true){
                        stopLoop = true;
                    }
                    firstIndex = G[i].indexOf(P[0], firstIndex+1);
                }
            }
            System.out.println(hit ? "YES" : "NO");
        }
    }
}

Solution in python3

Approach 1.

#!/bin/python3

import sys

def gridSearch(G, P,R,C,r,c):
    # Complete this function
    t=0
    for i in range(R-r+1):
        for j in range(C-c+1):
            for n in range(r):
                if G[i+n][j:j+c]!=P[n]:
                    t=0
                    break
                t+=1
            if t==r:
                return "YES"
    return "NO"

if __name__ == "__main__":
    t = int(input().strip())
    for a0 in range(t):
        R, C = input().strip().split(' ')
        R, C = [int(R), int(C)]
        G = []
        G_i = 0
        for G_i in range(R):
            G_t = str(input().strip())
            G.append(G_t)
        r, c = input().strip().split(' ')
        r, c = [int(r), int(c)]
        P = []
        P_i = 0
        for P_i in range(r):
            P_t = str(input().strip())
            P.append(P_t)
        result = gridSearch(G, P,R,C,r,c)
        print(result)

Approach 2.

#!/bin/python3

import sys
import re

def gridSearch(G, P):
    for g in range(len(G)):
        pos = occurencies(P[0], G[g])
        p = 1
        while len(pos) > 0 and p < len(P) and g + p < len(G):
            pos &= occurencies(P[p], G[g + p])
            p += 1
            
        if p == len(P) and len(pos) > 0:
            return "YES"
        
    return "NO"
        
def occurencies(val, text):
    return set(m.start() for m in re.finditer('(?={0})'.format(re.escape(val)), text))

if __name__ == "__main__":
    t = int(input().strip())
    for a0 in range(t):
        R, C = input().strip().split(' ')
        R, C = [int(R), int(C)]
        G = []
        G_i = 0
        for G_i in range(R):
           G_t = str(input().strip())
           G.append(G_t)
        r, c = input().strip().split(' ')
        r, c = [int(r), int(c)]
        P = []
        P_i = 0
        for P_i in range(r):
           P_t = str(input().strip())
           P.append(P_t)
        result = gridSearch(G, P)
        print(result)

Approach 3.

def check(G,P,ii,jj,pr,pc,gr,gc):
  # print(i,j)
  # print("********")
  pi=0
  pj=0
  # print(i,i+pr,j,j+pc)
  for i in range(ii,ii+pr):
    for j in range(jj,jj+pc):
      
      # print("==========")
      # print(i,j,pi,pj)
      # print(G[i][j],P[pi][pj])
      if G[i][j]!=P[pi][pj]:
        return False
      pj=pj+1
    pi=pi+1
    pj=0
  return True


def gridSearch(G, P):
  gr = len(G)
  if gr>0:
    gc=len(G[0])

  # print(gr)
  # print(gc)
  pr = len(P)

  if pr>0:
    pc=len(P[0])
  # print(pr)
  # print(pc)

  for i in range(gr-pr+1):
    for j in range(gc-pc+1):
      if G[i][j]==P[0][0]:
        if check(G,P,i,j,pr,pc,gr,gc):
          return 'YES'

  return 'NO' 

t = int(input().strip())
for a0 in range(t):
  R, C = input().strip().split(' ')
  R, C = [int(R), int(C)]
  G = []
  G_i = 0
  for G_i in range(R):
    G_t = str(input().strip())
    G.append(G_t)
  r, c = input().strip().split(' ')
  r, c = [int(r), int(c)]
  P = []
  P_i = 0
  for P_i in range(r):
    P_t = str(input().strip())
    P.append(P_t)
  result = gridSearch(G, P)
  print(result)

Solution in cpp

Approach 1.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int nt;
    cin >> nt;
    while(nt--) {
        int nr,nc;
        cin >> nr >> nc;
        char data[nr][nc];
        for(int i = 0; i < nr; ++i)
            for(int j = 0 ;j < nc; ++j)
              cin >> data[i][j];
        int nr2, nc2;
        cin >> nr2 >> nc2;
        char pattern[nr2][nc];
        for(int i = 0; i < nr2; ++i)
            for(int j = 0 ;j < nc2; ++j)
              cin >> pattern[i][j];
        bool matched = false;     
        for(int i = 0; i < nr - nr2 + 1 && !matched; ++i)              
            for(int j = 0; j < nc - nc2 + 1 && !matched; ++j) {
            bool flag = true;
            for(int p = 0; p < nr2 && flag; ++p)
                for(int q = 0; q <nc2 && flag; ++q)
                  if (pattern[p][q] != data[i + p][j + q])
                      flag = false;
            matched = flag;
        }
        cout << (matched ? "YES" : "NO") << endl;
    }
    return 0;
}

Approach 2.

#include<bits/stdc++.h>
using namespace std;

int pos_correct(int pos,string s){
    if(pos>=0 && pos<s.size())
        return 1;
    else return 0;

}

int checkpattern(int pos,int rowpos,const string m[],int R,const string p[],int r){
    int f;
    int i;
    int s=m[0].size();
    for(i=1;i<r;i++){
        f=-1;
        do{
            f=m[rowpos+i].find(p[i],f+1);
        }while(f<pos && pos_correct(f,m[0]));

        if(f!=pos)
            return 0;
    }

    return 1;
}

int myprog(){

        int C,R,c,r;

        cin>>R>>C;
        string *m=new string[R];
        int i;
        for(i=0;i<R;i++)
            cin>>m[i];
        cin>>r>>c;
        string *p=new string[r];
        for(i=0;i<r;i++)
            cin>>p[i];
        for(i=0;i<=R-r;i++){
            int pos=0;
            pos=m[i].find(p[0]);
            if(pos_correct(pos,m[i])){
                if(checkpattern(pos,i,m,R,p,r)){
                    return 1;
                }

            }

        }
    return 0;
}


int main()
{
    int t;
    cin>>t;
    while(t--){
        if(myprog())
            cout<<"YES";
        else
            cout<<"NO";
        cout<<endl;
    }

return 0;
}

Approach 3.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


bool findMatch(const vector<string> &G, const vector<string> &P) {
    int R = G.size();
    int C = G[0].length();
    int r = P.size();
    int c = P[0].length();
    for (int row = 0; row <= R-r; row++) {
        int i = G[row].find(P[0], 0);
        if (i == string::npos)
            continue;
        if (r == 1)
            return true;
        int matchedRows = 1;
        for (int col = i; col <= C-c; col++) {
            while (G[row+matchedRows].find(P[matchedRows], col) == col) {
                matchedRows++;
                if (matchedRows == r) {
                    return true;
                }
            }
            matchedRows = 0;
        }
    }
    return false;
}

int main() {
    int T, R, C, r, c;
    cin >> T;
    vector<string> G, P;
    for (int t = 0; t < T; t++) {
        cin >> R >> C;
        for (int i = 0; i < R; i++) {
            char row[C+1];
            row[C] = 0;
            cin >> row;
            G.push_back(string(row));
        }
        cin >> r >> c;
        for (int i = 0; i < r; i++) {
            char row[c+1];
            row[c] = 0;
            cin >> row;
            P.push_back(string(row));
        }
        cout << ((findMatch(G, P)) ? "YES" : "NO") << endl;
        G.clear();
        P.clear();
    }
    return 0;
}