search a pattern in a 2D matrix

Question

This is an interview question

You have to find a string in two-dimensional array. The input contains 2-D array of characters and given string. You can move in one of eight directions . The output contains location of first letter of string if string found completely, otherwise return -1. Any one out of multiple answers is accepted, if possible.

For example, Input:

b t g
p a d
r k j

String: rat
Output: (2,0)

I tried this but getting wrong output for

 5 5
    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

    MICROSOFT

please help

#include<iostream>
#include<string>
using namespace std;
bool isInside(int x,int y,int m,int n)
{
    if(x>=0&&x<m&&y>=0&&y<n)return true;
    return false;
}
void findString(char mat[10][10],int m,int n,string str)
{
    int i,j;

    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
    {
        int k=0,x=i,y=j;
        bool flag=true;
        if(mat[i][j]==str[k])
        {
            while(flag&&k<str.size())
            {
                int x1=x-1,x2=x+1,y1=y-1,y2=y+1;
                if(isInside(x1,y1,m,n)&&mat[x1][y1]==str[k])
                    {
                        x=x1; y=y1; k++;
                    }
                else if(isInside(x1,y,m,n)&&mat[x1][y]==str[k])
                    {
                        x=x1; y=y; k++;
                    }
                else if(isInside(x1,y2,m,n)&&mat[x1][y2]==str[k])
                    {
                        x=x1; y=y2; k++;
                    }
                else if(isInside(x,y1,m,n)&&mat[x][y1]==str[k])
                    {
                        x=x; y=y1; k++;
                    }
                else if(isInside(x,y2,m,n)&&mat[x][y2]==str[k])
                    {
                        x=x; y=y2; k++;
                    }
                else if(isInside(x2,y1,m,n)&&mat[x2][y1]==str[k])
                    {
                        x=x2; y=y1; k++;
                    }
                else if(isInside(x2,y,m,n)&&mat[x2][y]==str[k])
                    {
                        x=x2; y=y; k++;
                    }
                else if(isInside(x2,y2,m,n)&&mat[x2][y2]==str[k])
                    {
                        x=x2; y=y2; k++;
                    }
                else flag=false;
            }
            if(flag==true)
            {
                cout<<endl<<"\("<<i<<","<<j<<")"<<endl;
                return;
            }
        }
    }
    cout<<endl<<"-1"<<endl;
    return;
}
int main()
{
    int i,j,n,m;
    char mat[10][10];
    string str;
    cout<<"enter the dimention of the matrix: ";
    cin>>m>>n;
    cout<<endl<<"enter the char matrix:"<<endl;
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
        cin>>mat[i][j];
    cout<<endl<<"enter the test string: ";
    cin>>str;
    findString(mat,m,n,str);
    return 0;
}

Answer 1

Your search is not complete because from a given position you only try one valid neighbor.

For instance, starting from M, if you follow only the bottom I, search will stop there; you need to try the top right I as well, and this calls for a recursive solution.

Your solution also does not forbid to pass twice by the same character, I am not sure if this is legal.

Pseudocode:

Try(i, j, Suffix):
  if i < 0 or i >= m or j < 0 or j >= n:
    # No such position
    return

  if Mat[i][j] == Suffix[0]:
    if len(Suffix) == 1:
      # The whole string was matched
      print "Found !"
      return

    # Mark the position (optional)
    Mat[i][j]= uppercase(Mat[i][j])

    # Try all 8 neighbors
    Try(i+1, j, Suffix[1:])
    Try(i+1, j+1, Suffix[1:])
    Try(i, j+1, Suffix[1:])
    ...

    # Unmark the position (optional)
    Mat[i][j]= lowercase(Mat[i][j])

You call it with

for i in range(m):
  for j in range(n):
    Try(i, j, String)