Find a string in a 2D matrix

+2 votes
asked in Interview Question by shivani

You are given a 2D array of characters and  a string.Find if string is present in 2D array. String can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return true if match is found,  false if you can not find. 

eg : 

Matrix 
{'A','C','P','R','C'}, 
{'X','S','O','P','C'}, 
{'V','O','V','N','I'}, 
{'W','G','F','M','N'}, 
{'Q','A','T','I','T'} 


And the pattern is Microsoft. 

 

Add question to:

1 Answer

+2 votes
answered by vivek_23
selected by admin
 
Best answer

Assumption: All characters are uppercase letters from A-Z.
Java Solution using Depth First Search: 

Explanation- 

1) We just go through each character in the 2D char array and check if any char matches the first index of the String. If yes, it might be the seed or you can say the root for the zigzag 8 directional match. 

2) So, once first character is found, we search in all 8 directions for "every consecutive character in the string" . If any of these paths returns a true, we "immediately" return true.

3) As mentioned in the problem statement that a single char in the array cannot be used more than once, we maintain a boolean path array to make sure that if we visit an index again, we just return false. 

Optimization- 

These 2 lines are redundant. We can reduce the runtime ms a bit.

int[] hash = new int[26];
for(int i=0;i<len;++i) hash[s.charAt(i)-'A']++;
 

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 sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        char[][] ch = new char[N][];

        for(int i=0;i<N;++i){
        	ch[i] = sc.nextLine().toCharArray();
        }

        System.out.println(isStringPresent(ch,sc.nextLine()));
    }

    public static boolean isStringPresent(char[][] ch, String s){
    	int len    = s.length();
    	int[] hash = new int[26];
    	for(int i=0;i<len;++i) hash[s.charAt(i)-'A']++;
    	int rows = ch.length;
    	int cols = ch[0].length;
    	boolean[][] path = new boolean[rows][cols]; 

    	for(int i=0;i<rows;++i){
    		for(int j=0;j<cols;++j){
    			if(ch[i][j] == s.charAt(0) && dfs(ch,i,j,s,0,len,path)) return true;
    		}
    	}

    	return false;
    }

    public static boolean dfs(char[][] ch,int row,int col,String s,int index,int len,boolean[][] path){
	    if(	   
	    	row >= ch.length || 
	    	row < 0 || 
    	    col >= ch[0].length || 
    	    col < 0 || 
    	    index > len || 
    	    path[row][col] || 
    	    ch[row][col] != s.charAt(index)
    	   )
    	{
    		return false;
    	}

    	if(index + 1 == len) return true;

    	path[row][col] = true;
    	boolean found = dfs(ch,row-1,col-1,s,index+1,len,path) ||
    					dfs(ch,row-1,col,s,index+1,len,path) || 
    					dfs(ch,row-1,col+1,s,index+1,len,path) ||
    					dfs(ch,row,col-1,s,index+1,len,path) ||
    					dfs(ch,row,col+1,s,index+1,len,path) ||
    					dfs(ch,row+1,col-1,s,index+1,len,path) ||
    					dfs(ch,row+1,col,s,index+1,len,path) ||
    					dfs(ch,row+1,col+1,s,index+1,len,path);
    	path[row][col] = false;
    	return found;
    }
}

Let me know if it fails for any test case. 
Input I have considered for this program. 
5
ACPRC
XSOPC
VOVNI
WGFMN
QATIT
MICROSOFT

  1. where 5 is number of strings in each row
  2. Last word is string to be searched.
commented by shivani
Thank you very much.
commented by vivek_23
Thank you very much for choosing my solution as an answer. I will see and contribute to other questions as well  .
commented by shivani
It is always nice to see great logic :)
...