Finden eines 2D-Arrays in einem größeren 2D-Array

Question

Ich bin in der Lage, das Problem für die Testfälle zu lösen, wo es nur 1 String pro Zeile gibt. Aber ich scheitere, wenn mehrere Strings in einer einzigen Zeile sind.

Zum Beispiel:

Test Case Typ 1:

Big Matrix:

7283455864 
6731158619 
8988242643 
3830589324 
2229505813 
5633845374 
6473530293 
7053106601 
0834282956 
4607924137 

Kleine Matrix:

9505 
3845 
3530 

passiere ich diese Art von Testfällen als 9505 auftritt höchstens einmal in Big Matrix.

Test Case Typ: 2

Big Matrix:

7652157548860692421022503 
9283597467877865303553675 
4160389485250089289309493 
2583470721457150497569300 
3220130778636571709490905 
3588873017660047694725749 
9288991387848870159567061 
4840101673383478700737237 
8430916536880190158229898 
8986106490042260460547150 
2591460395957631878779378 
1816190871689680423501920 
0704047294563387014281341 
8544774664056811258209321 
9609294756392563447060526 
0170173859593369054590795 
6088985673796975810221577 
7738800757919472437622349 
5474120045253009653348388 
3930491401877849249410013 
1486477041403746396925337 
2955579022827592919878713 
2625547961868100985291514 
3673299809851325174555652 
4533398973801647859680907 

Kleine Matrix:

5250 
1457 
8636 
7660 
7848 

ich nicht diese Art von Testfällen, wo 5250 (oder jede andere Zeile in kleinen Matrix) tritt mehr als einmal in derselben Zeile der größeren Matrix auf:

Unten ist der Code i habe geschrieben:

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

     HashMap<Integer,Integer> rowCol=new HashMap();  
     Scanner in = new Scanner(System.in); 
     int t = in.nextInt(); 
     for(int a0 = 0; a0 < t; a0++){ 
      //bigger array 
      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(); 
      } 
      //smaller array 
      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(); 
      } 

      for(int i = 0;i<R-r;i++)//obvious 
      { 
       for(int j = 0; j<r;j++)//obvious 
       { 
        //if string found put in map(row at which found,column at whch found) 
        if(G[i].indexOf(P[j])>=0)//string found 
        { 
         rowCol.put(i,G[i].indexOf(P[j])); 
        } 
       } 
      } 

      //now check if rows are consecutive(1,2,3) and columns are equal(1,1,1) 
      HashSet<Integer> mc = new HashSet<Integer>(rowCol.values());//if size==1 then same column 
      ArrayList<Integer> mr = new ArrayList<Integer>(rowCol.keySet()); 
      int count = 0; 
      for(int m = 0 ;m<mr.size()-1;m++)//checking if keys are consecutive 
      { 

       if(mr.get(m)+1==mr.get(m+1)) 
       { 
        count++;//how many values are same ,hw mny strings found at same index 
       } 
      } 

      //System.out.println(count+"+++++"+(mr.size()-1)); 
      //System.out.println(rowCol.values().size()+"==="+r); 

      if(mc.size()==1 && count==(mr.size()-1) && rowCol.keySet().size()==r)//all column same && all rows are consecutive && 
      { 
       System.out.println("YES"); 
      } 
      else 
      { 
       System.out.println("NO"); 
      } 


     } 


    } 
} 

Answer 1

Ihre Logik ist fehlerhaft.

for(int i = 0;i<R-r;i++)//obvious 
    { 
     for(int j = 0; j<r;j++)//obvious 
     { 
      //if string found put in map(row at which found,column at whch found) 
      if(G[i].indexOf(P[j])>=0)//string found 
      { 
       rowCol.put(i,G[i].indexOf(P[j])); 
      } 
     } 
    } 

Dies geht durch alle Linien in G, und alle Linien von P. Wenn diese Zeile von P in dieser Zeile von G existiert, wird sie in der Karte platziert werden.

Aber zuerst, es sagt Ihnen nur, dass einige Zeile von P ist in dieser Zeile von G, es sagt Ihnen nicht, welche Zeile. Dies bedeutet, dass es auch fehlschlägt, wenn Sie nach einer kleinen Matrix suchen, die genau wie eine bestehende Matrix ist, aber eine andere Reihenfolge der Linien.

Zweitens, wenn es mehr als eine Zeile der kleinen Matrix in der Zeile von G gibt, behält es den Index der unteren Zeile von P. Das heißt, wenn Sie beide 5250 und 7660 in der gleichen Zeile haben G, wird es nur den Index des 7660 halten und die 5250.

ArrayList<Integer> mr = new ArrayList<Integer>(rowCol.keySet()); 

ignorieren Sie mr verwenden für aufeinanderfolgende Zeile zu überprüfen, aber Sie es mit dem Schlüsselsatz aus einem HashMap füllen. Dies bedeutet, dass die Reihenfolge nicht garantiert ist - Sie könnten die Zeilennummern in der Reihenfolge 5,3,1,2,4 oder was auch immer bekommen.

Sie sollten Ihr Programm mit unterschiedlicher Logik schreiben. Versuchen Sie nicht, alle Standorte aller Linien zu sammeln. Suchen Sie den Ort der ersten Zeile von P und überprüfen Sie sofort, ob der Rest vorhanden ist. Nehmen wir an, Sie haben die erste Zeile von P in Zeile 30 bei Index 15 gefunden. Prüfen Sie dann, ob Zeile 2 in Zeile 31 bei Index 15 und Zeile 3 in Zeile 32 bei Index 15 ist und so weiter.

Wenn alle übereinstimmten, geben Sie "YES" und von der Methode zurück. Fahren Sie nicht mit der Schleife fort. Wenn nicht alle übereinstimmen, suchen Sie weiter nach P [0].

• Hinweis, dass es möglicherweise mehr als ein Vorkommen von P [0] in der gleichen Zeile in G. Also, wenn Matching ausgefallen ist, auch weiterhin in der gleichen Zeile von G bis keine weiteren Vorkommen von P suchen [0] auftreten, und dann nur in die nächste Zeile von G.
• Wenn Sie keine Übereinstimmungen gefunden haben, dann am Ende der Schleife können Sie "NEIN" drucken.