Wednesday, August 18, 2010

Microsoft Question: There exists 2D char array, We need to find out whether a given string("microsoft") exists in the given matrix. the string can be vertical or horizontal..but NOT diagonal

I think it can be achieved with straight forward recursive programming. Following is my solution --


char grid[10][10]={      // 2D Array in which string has to be searched
"maaaaaaaa",
"iaataaaaa",
"crafaaaaa",
"rssoftaaa",
"osaaaaaaa",
"tofaaaaaa",
"oataaaaaa",
"faaaaaaaa",
"taaaaaaaa",
"aaaaaaaaa"
};

int check(int i,int j,char ch)
{
    if(i>=0 &&  i<10 && j>=0 && j<10 && grid[i][j]==ch )
           return 1;
    return 0;
}

void Search(int i,int j,char str[],int l)
{

    if(check(i+1,j,str[l])==1)
    {
        if(l==8)
            cout<<"string found\n\n";
        else
            Search(i+1,j,str,l+1);

    }
    if(check(i-1,j,str[l])==1)
    {
        if(l==8)
            cout<<"string found\n\n";
        else
            Search(i-1,j,str,l+1);

    }
    if(check(i,j+1,str[l])==1)
    {
        if(l==8)
            cout<<"string found\n\n";
        else
            Search(i,j+1,str,l+1);

    }
    if(check(i,j-1,str[l])==1)
    {
        if(l==8)
            cout<<"string found\n\n";
        else
            Search(i,j-1,str,l+1);
    }
    return;
}

int main()
{
    char str[10]="microsoft";              //string to be searched
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(grid[i][j]==str[0])
                Search(i,j,str,1);
    return 0;
}

2 comments:

  1. sir, in this problem string can be either vertical only or horizontal only. this program is serching string as
    "|m| a a a a a a a a",
    "|i| a a t a a a a a",
    "|c| r a f a a a a a",
    "|r| s s o f t a a a",
    "|o||s| a a a a a a a",
    " t |o||f|a a a a a a",
    " o a |t|a a a a a a",
    " f a a a a a a a a",
    " t a a a a a a a a",
    " a a a a a a a a a"

    ReplyDelete
  2. Again there is mistake in Problem Statement.
    Thanks for mentioning it.

    ReplyDelete