Epic Systems Interview Question Software Engineer / Developers
Country: United States
Can the word only be present entirely in a row/column/diagonal? cant it be across multiple rows and columns?
For the diagonals, you have only implemented the logic for the diagonal going from top-left to bottom-right. You also need to implement it for the other diagonal going from top-right to bottom-left.
Other than that, perfect solution!
When scanning the rows, what if the matrix contains aab and the word we are looking for is ab ?
when j==0, charPoint will be 1.
when j==1, charPoint will be 0. But we again need to compare the chars[0] with matrix[0][1] right ?
I don't think that is being compared.
This doesn't work if the last character is incorrect. For example, in the array
char[][] matrix = {{'a','b','c'},{'d','e', 'f'}, {'g','h','i'}};
If you enter in the word: "abp", the function returns true
import java.io.*;
import java.util.*;
public class Matrix_pattern_search
{
static char a[][]= { {'\0','\0','\0','\0','\0','\0','\0'},
{'\0','r','o','h','d','n','\0'},
{'\0','b','o','x','a','p','\0'},
{'\0','a','r','h','a','c','\0'},
{'\0','r','o','h','a','n','\0'},
{'\0','r','m','j','i','o','\0'},
{'\0','\0','\0','\0','\0','\0','\0'}};// instance variables - replace the example below with your own
static String s="han";
public static void main()
{
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
System.out.print(a[i][j]+" ");
}
System.out.println();
}
System.out.println();
for(int i=1;i<a.length;i++)
{
for(int j=1;j<a[i].length;j++)
{
if(a[i][j]==s.charAt(0))
search(i,j);
}
}
}
static void search(int i,int j)
{
int k=1;
if(a[i-1][j-1]==s.charAt(k))
go_towards(i-1,j-1,1);
else if(a[i-1][j]==s.charAt(k))
go_towards(i-1,j,2);
else if(a[i-1][j+1]==s.charAt(k))
go_towards(i-1,j+1,3);
else if(a[i][j+1]==s.charAt(k))
go_towards(i,j+1,4);
else if(a[i+1][j+1]==s.charAt(k))
go_towards(i+1,j+1,5);
else if(a[i+1][j]==s.charAt(k))
go_towards(i+1,j,6);
else if(a[i+1][j-1]==s.charAt(k))
go_towards(i+1,j-1,7);
else if(a[i][j-1]==s.charAt(k))
go_towards(i,j-1,8);
}
static void go_towards(int i,int j,int c)
{
int flag=0;
int k=2;
int i1,j1;
switch(c)
{
case 1: i1=i+1;
j1=j+1;
while(k<s.length())
{
if(a[--i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 2: i1=i+1;
j1=j;
while(k<s.length())
{
if(a[--i][j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 3: i1=i+1;
j1=j-1;
while(k<s.length())
{
if(a[--i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 4: i1=i;
j1=j-1;
while(k<s.length())
{
if(a[i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 5:
i1=i-1;
j1=j-1;
while(k<s.length())
{
if(a[++i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 6: i1=i-1;
j1=j;
while(k<s.length())
{
if(a[++i][j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 7: i1=i-1;
j1=j+1;
while(k<s.length())
{
if(a[++i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 8:i1=i;
j1=j+1;
while(k<s.length())
{
if(a[i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
}
}
}
import java.io.*;
import java.util.*;
public class Matrix_pattern_search
{
static char a[][]= { {'\0','\0','\0','\0','\0','\0','\0'},
{'\0','r','o','h','d','n','\0'},
{'\0','b','o','x','a','p','\0'},
{'\0','a','r','h','a','c','\0'},
{'\0','r','o','h','a','n','\0'},
{'\0','r','m','j','i','o','\0'},
{'\0','\0','\0','\0','\0','\0','\0'}};// instance variables - replace the example below with your own
static String s="han";
public static void main()
{
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
System.out.print(a[i][j]+" ");
}
System.out.println();
}
System.out.println();
for(int i=1;i<a.length;i++)
{
for(int j=1;j<a[i].length;j++)
{
if(a[i][j]==s.charAt(0))
search(i,j);
}
}
}
static void search(int i,int j)
{
int k=1;
if(a[i-1][j-1]==s.charAt(k))
go_towards(i-1,j-1,1);
else if(a[i-1][j]==s.charAt(k))
go_towards(i-1,j,2);
else if(a[i-1][j+1]==s.charAt(k))
go_towards(i-1,j+1,3);
else if(a[i][j+1]==s.charAt(k))
go_towards(i,j+1,4);
else if(a[i+1][j+1]==s.charAt(k))
go_towards(i+1,j+1,5);
else if(a[i+1][j]==s.charAt(k))
go_towards(i+1,j,6);
else if(a[i+1][j-1]==s.charAt(k))
go_towards(i+1,j-1,7);
else if(a[i][j-1]==s.charAt(k))
go_towards(i,j-1,8);
}
static void go_towards(int i,int j,int c)
{
int flag=0;
int k=2;
int i1,j1;
switch(c)
{
case 1: i1=i+1;
j1=j+1;
while(k<s.length())
{
if(a[--i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 2: i1=i+1;
j1=j;
while(k<s.length())
{
if(a[--i][j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 3: i1=i+1;
j1=j-1;
while(k<s.length())
{
if(a[--i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 4: i1=i;
j1=j-1;
while(k<s.length())
{
if(a[i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 5:
i1=i-1;
j1=j-1;
while(k<s.length())
{
if(a[++i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 6: i1=i-1;
j1=j;
while(k<s.length())
{
if(a[++i][j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 7: i1=i-1;
j1=j+1;
while(k<s.length())
{
if(a[++i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 8:i1=i;
j1=j+1;
while(k<s.length())
{
if(a[i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
}
}
}
import java.io.*;
import java.util.*;
public class Matrix_pattern_search
{
static char a[][]= { {'\0','\0','\0','\0','\0','\0','\0'},
{'\0','r','o','h','d','n','\0'},
{'\0','b','o','x','a','p','\0'},
{'\0','a','r','h','a','c','\0'},
{'\0','r','o','h','a','n','\0'},
{'\0','r','m','j','i','o','\0'},
{'\0','\0','\0','\0','\0','\0','\0'}};// instance variables - replace the example below with your own
static String s="han";
public static void main()
{
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
System.out.print(a[i][j]+" ");
}
System.out.println();
}
System.out.println();
for(int i=1;i<a.length;i++)
{
for(int j=1;j<a[i].length;j++)
{
if(a[i][j]==s.charAt(0))
search(i,j);
}
}
}
static void search(int i,int j)
{
int k=1;
if(a[i-1][j-1]==s.charAt(k))
go_towards(i-1,j-1,1);
else if(a[i-1][j]==s.charAt(k))
go_towards(i-1,j,2);
else if(a[i-1][j+1]==s.charAt(k))
go_towards(i-1,j+1,3);
else if(a[i][j+1]==s.charAt(k))
go_towards(i,j+1,4);
else if(a[i+1][j+1]==s.charAt(k))
go_towards(i+1,j+1,5);
else if(a[i+1][j]==s.charAt(k))
go_towards(i+1,j,6);
else if(a[i+1][j-1]==s.charAt(k))
go_towards(i+1,j-1,7);
else if(a[i][j-1]==s.charAt(k))
go_towards(i,j-1,8);
}
static void go_towards(int i,int j,int c)
{
int flag=0;
int k=2;
int i1,j1;
switch(c)
{
case 1: i1=i+1;
j1=j+1;
while(k<s.length())
{
if(a[--i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 2: i1=i+1;
j1=j;
while(k<s.length())
{
if(a[--i][j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 3: i1=i+1;
j1=j-1;
while(k<s.length())
{
if(a[--i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 4: i1=i;
j1=j-1;
while(k<s.length())
{
if(a[i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 5:
i1=i-1;
j1=j-1;
while(k<s.length())
{
if(a[++i][++j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 6: i1=i-1;
j1=j;
while(k<s.length())
{
if(a[++i][j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 7: i1=i-1;
j1=j+1;
while(k<s.length())
{
if(a[++i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
case 8:i1=i;
j1=j+1;
while(k<s.length())
{
if(a[i][--j]!=s.charAt(k))
{
flag=1; break;
}
k++;
}
if(flag==0)
System.out.println("String: "+ s +" is present at index: ["+i1+","+j1+"]");
break;
}
}
}
Some rather inelegant solutions here.
char arr[] = {'a', 'b', 'c', 'd',
'e', 'f', 'g', 'h',
'i', 'j', 'k', 'l',
'm', 'n', 'o', 'p' };
char* strstr_stride(int n, char* pStr, int stride, char* pSubStr)
{
for(int j = 0; n-j >= strlen(pSubStr); pStr += stride,j++)
{
int i = 0;
for (; pSubStr[i] && (pStr[i*stride] == pSubStr[i]); i++);
if (!pSubStr[i])
return pStr;
}
return NULL;
}
bool CheckMat(char* pMat, int n, char* pSearch)
{
for (int i = 0; i < n; i++) //horiz & vert
if (strstr_stride(n, pMat + n*i, 1, pSearch) || strstr_stride(n, pMat + i, n, pSearch))
return true;
return strstr_stride(n, pMat, n+1, pSearch) || strstr_stride(n, pMat+n-1, n-1, pSearch); //diags
}
void main()
{
char* test[] = {"nop", "nope", "dgj", "dgk"};
for (int i = 0; i < sizeof(test)/sizeof(test[0]); i++)
printf("%s = %d\n", test[i], CheckMat(arr, 4, test[i]));
getch();
}
// I assume diagonal only means upper-left to lower-right.
typedef char matrix[N][N];
bool find(string word, matrix a){
string::size_type len =word.length();
for (int i=0; i< N; ++i) {
for (int j=0 ; j< N; ++j) {
if (a[i][j]==word[0]){
bool horizontal=true;
bool vertical=true;
bool diagonal=true;
for (int k=1; k< len; ++k){
if (j+k>= N || word[k]!= a[i][j+k]) { horizontal= false; break;}
}
if (horizontal ==true) return true;
for (int k=1; k< len; ++k){
if (i+k>= N || word[k]!= a[i+k][j]) { vertical = false; break;}
}
if (vertical ==true) return true;
for (int k=1; k<len; ++k){
if (i+k>= N || j+k>= N || word[k]!= a[i+k][j+k]) { diagonal = false; break;}
}
if (diagonal == true) return true;
}
}
}
return false;
}
import java.util.Scanner;
public class MatrixDic{
static char a[][]= { {'r','o','h','d','n'},
{'b','o','x','a','p'},
{'a','r','h','a','c'},
{'r','o','h','a','n'},
{'r','m','j','i','o'} };
public static void main(String []args){
Scanner in=new Scanner(System.in);
String str=in.nextLine();
int f=0;
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
if(a[i][j]==str.charAt(0))
f=find(i,j,str);
if(f==1){
break;
}
}
}
if(f==0)
System.out.print("false");
else{
System.out.print("true");
}
}
public static int find(int i,int j,String str){
int k=1;
int fl=0;
//row forword
for(;k<str.length();k++){
j++;
if(j<5){
if(a[i][j]==str.charAt(k))
fl=1;
else
fl=0;
}
}
//row backword
if(fl==0){
for(;k<str.length();k++){
j--;
if(j>=0){
if(a[i][j]==str.charAt(k))
fl=1;
else
fl=0;
}
}
}
//col forword
if(fl==0){
for(;k<str.length();k++){
i++;
if(i<5){
if(a[i][j]==str.charAt(k))
fl=1;
else
fl=0;
}
}
}
// col backword
if(fl==0){
for(;k<str.length();k++){
i--;
if(i>=0){
if(a[i][j]==str.charAt(k))
fl=1;
else
fl=0;
}
}
}
//dia forword
if(fl==0){
for(;k<str.length();k++){
j++; i++;
if(j<5&&i<5){
if(a[i][j]==str.charAt(k))
fl=1;
else
fl=0;
}
}
}
//dia backword
if(fl==0){
for(;k<str.length();k++){
j--;i--;
if(i>=0&&j>=0){
if(a[i][j]==str.charAt(k))
fl=1;
else
fl=0;
}
}
}
return fl;
}
}
public class wordinMatrix {
public static boolean find(char[][] matrix, int[] index, char c)
{
for(int i=0; i<matrix.length; i++)
{
for(int j=0; j<matrix[i].length; j++)
{
if(matrix[i][j]==c)
{
index[0] = i;
index[1] = j;
return true;
}
}
}
return false;
}
public static void main(String[] args)
{
char matrix[][] = {{'n','a','h','i'},
{'o','u','i','f'},
{'n','t','d','a'},
{'e','i','e','e'}};
//String str = "nude";
String str = "none";
if(str.length()>4)
{
System.out.println("String is invalid");
return;
}
int [] index = new int [2];
if(find(matrix, index, str.charAt(0)))
{
System.out.println("Checking");
int i = index[0];
int j = index[1] + 1;
System.out.println(i+","+j);
boolean flag = true;
// col check
for(int k=1; j<matrix.length; j++,k++)
{
if(str.charAt(k)!=matrix[i][j])
{
flag = false;
break;
}
}
if(flag == true)
{
System.out.println("Found in Column");
return;
}
// row check
i = index[0] + 1;
j = index[1];
flag = true;
for(int k=1; i<matrix.length; i++,k++)
{
if(str.charAt(k)!=matrix[i][j])
{
flag = false;
break;
}
}
if(flag == true)
{
System.out.println("Found in Row");
return;
}
// diagonal check
flag = true;
i = index[0] + 1;
j = index[1] + 1;
for(int k=1; i<matrix.length && j<matrix.length; i++,j++,k++)
{
if(str.charAt(k)!=matrix[i][j])
{
flag = false;
break;
}
}
if(flag == true)
{
System.out.println("Found in Diagonal");
return;
}
}
}
}
/*
*
* You are given an N*N matrix. The matrix contains characters.
* Write a program to find a word in the matrix.
* The word can be found in either the rows or columns or the diagonals.
* The program should return true if the word is found and false if the word is not found.
*/
package CareerCup;
public class Check_Word_in_Matrix {
private static Character[][] matrix={{'a','d','i','t','y','a'}, {'n','i','k','h','i','l'},
{'s','u','b','o','d','h'},{'k','a','m','s','u','k'},{'r','a','g','h','u','g'},{'g','h','i','m','a','n'}
};
public static void main(String[] args) {
String word="raghug";
System.out.println("Word found is : " + isWordFound(word));
}
private static boolean isWordFound(String input) {
if(input==null)
return false;
if(input.length() > matrix.length)
return false;
Character x=input.charAt(0);
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix.length;j++)
{
if(matrix[i][j]==x) //If match is found for first character
{
if(checkRightDiagonal(input,i,j) || checkLeftDiagonal(input,i,j) || checkRight(input,i,j) || checkDown(input,i,j) )
{
return true;
}
}
}
}
return false;
}
private static boolean checkRightDiagonal(String input, int row, int column) {
/*
* If the length is greater than the input, there is no match, simply return false
*/
if( row+input.length() > matrix.length || column +input.length() > matrix.length )
{
return false;
}
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][++column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkRightDiagonal" );
return true;
}
private static boolean checkLeftDiagonal(String input, int row, int column) {
if(column < input.length()-1)
{
return false;
}
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][--column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkLeftDiagonal" );
return true;
}
private static boolean checkDown(String input, int row, int column) {
if(column + input.length() > matrix.length )
return false;
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkDown" );
return true;
}
private static boolean checkRight(String input, int row, int column) {
if(column +input.length() > matrix.length)
return false;
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[row][++column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkRight" );
return true;
}
}
/*
*
* You are given an N*N matrix. The matrix contains characters.
* Write a program to find a word in the matrix.
* The word can be found in either the rows or columns or the diagonals.
* The program should return true if the word is found and false if the word is not found.
*/
package CareerCup;
public class Check_Word_in_Matrix {
private static Character[][] matrix={{'a','d','i','t','y','a'}, {'n','i','k','h','i','l'},
{'s','u','b','o','d','h'},{'k','a','m','s','u','k'},{'r','a','g','h','u','g'},{'g','h','i','m','a','n'}
};
public static void main(String[] args) {
String word="raghug";
System.out.println("Word found is : " + isWordFound(word));
}
private static boolean isWordFound(String input) {
if(input==null)
return false;
if(input.length() > matrix.length)
return false;
Character x=input.charAt(0);
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix.length;j++)
{
if(matrix[i][j]==x) //If match is found for first character
{
if(checkRightDiagonal(input,i,j) || checkLeftDiagonal(input,i,j) || checkRight(input,i,j) || checkDown(input,i,j) )
{
return true;
}
}
}
}
return false;
}
private static boolean checkRightDiagonal(String input, int row, int column) {
/*
* If the length is greater than the input, there is no match, simply return false
*/
if( row+input.length() > matrix.length || column +input.length() > matrix.length )
{
return false;
}
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][++column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkRightDiagonal" );
return true;
}
private static boolean checkLeftDiagonal(String input, int row, int column) {
if(column < input.length()-1)
{
return false;
}
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][--column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkLeftDiagonal" );
return true;
}
private static boolean checkDown(String input, int row, int column) {
if(column + input.length() > matrix.length )
return false;
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkDown" );
return true;
}
private static boolean checkRight(String input, int row, int column) {
if(column +input.length() > matrix.length)
return false;
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[row][++column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkRight" );
return true;
}
}
{
public class Check_Word_in_Matrix {
private static Character[][] matrix={{'a','d','i','t','y','a'}, {'n','i','k','h','i','l'},
{'s','u','b','o','d','h'},{'k','a','m','s','u','k'},{'r','a','g','h','u','g'},{'g','h','i','m','a','n'}
};
public static void main(String[] args) {
String word="raghug";
System.out.println("Word found is : " + isWordFound(word));
}
private static boolean isWordFound(String input) {
if(input==null)
return false;
if(input.length() > matrix.length)
return false;
Character x=input.charAt(0);
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix.length;j++)
{
if(matrix[i][j]==x) //If match is found for first character
{
if(checkRightDiagonal(input,i,j) || checkLeftDiagonal(input,i,j) || checkRight(input,i,j) || checkDown(input,i,j) )
{
return true;
}
}
}
}
return false;
}
private static boolean checkRightDiagonal(String input, int row, int column) {
/*
* If the length is greater than the input, there is no match, simply return false
*/
if( row+input.length() > matrix.length || column +input.length() > matrix.length )
{
return false;
}
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][++column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkRightDiagonal" );
return true;
}
private static boolean checkLeftDiagonal(String input, int row, int column) {
if(column < input.length()-1)
{
return false;
}
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][--column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkLeftDiagonal" );
return true;
}
private static boolean checkDown(String input, int row, int column) {
if(column + input.length() > matrix.length )
return false;
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkDown" );
return true;
}
private static boolean checkRight(String input, int row, int column) {
if(column +input.length() > matrix.length)
return false;
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[row][++column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkRight" );
return true;
}
}
}
{
public class Check_Word_in_Matrix {
private static Character[][] matrix={{'a','d','i','t','y','a'}, {'n','i','k','h','i','l'},
{'s','u','b','o','d','h'},{'k','a','m','s','u','k'},{'r','a','g','h','u','g'},{'g','h','i','m','a','n'}
};
public static void main(String[] args) {
String word="raghug";
System.out.println("Word found is : " + isWordFound(word));
}
private static boolean isWordFound(String input) {
if(input==null)
return false;
if(input.length() > matrix.length)
return false;
Character x=input.charAt(0);
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix.length;j++)
{
if(matrix[i][j]==x) //If match is found for first character
{
if(checkRightDiagonal(input,i,j) || checkLeftDiagonal(input,i,j) || checkRight(input,i,j) || checkDown(input,i,j) )
{
return true;
}
}
}
}
return false;
}
private static boolean checkRightDiagonal(String input, int row, int column) {
/*
* If the length is greater than the input, there is no match, simply return false
*/
if( row+input.length() > matrix.length || column +input.length() > matrix.length )
{
return false;
}
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][++column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkRightDiagonal" );
return true;
}
private static boolean checkLeftDiagonal(String input, int row, int column) {
if(column < input.length()-1)
{
return false;
}
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][--column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkLeftDiagonal" );
return true;
}
private static boolean checkDown(String input, int row, int column) {
if(column + input.length() > matrix.length )
return false;
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[++row][column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkDown" );
return true;
}
private static boolean checkRight(String input, int row, int column) {
if(column +input.length() > matrix.length)
return false;
int count=input.length()-1;
int charcount=1;
while(count!=0)
{
if(matrix[row][++column]==input.charAt(charcount)) //If match is found for first character
{
count--;
charcount++;
}
else
{
return false;
}
}
System.out.println("Word found in method : checkRight" );
return true;
}
}
}
public class findWordIn2Darray {
public static void main(String Args[]){
char[][] matrix = {{'a','b','c'},{'d','e', 'f'}, {'g','h','i'}};
boolean f = findWord(matrix,"aei");
System.out.println(f);
}
public static boolean findWord(char[][] matrix, String word) {
char[] chars = word.toCharArray();
int rowLen = matrix.length;
int colLen = matrix[0].length;
if (word.length() > rowLen || word.length() > colLen) {
return false;
}
int charPoint = 0;
//Scan rows
for(int i = 0; i < rowLen; i++){
for(int j = 0; j < colLen; j++){
System.out.println(matrix[i][j]);
if(matrix[i][j] != chars[charPoint]){
charPoint = 0;
continue;
} else {
if(chars[charPoint] == chars[word.length()-1]){
return true;
}
charPoint++;
}
}
}
//Scan columns;
for(int j = 0; j < colLen; j++){
for(int i = 0; i < rowLen; i++){
System.out.println(matrix[i][j]);
if(matrix[i][j] != chars[charPoint]){
charPoint = 0;
continue;
} else {
if(chars[charPoint] == chars[word.length()-1]){
return true;
}
charPoint++;
}
}
}
//Scan Diagonal(Top left to bottom right)
for(int i = 0; i < rowLen; i++){
System.out.println(matrix[i][i]);
if(matrix[i][i] != chars[charPoint]){
charPoint = 0;
continue;
} else {
if(chars[charPoint] == chars[word.length()-1]){
return true;
}
charPoint++;
}
}
//Scan Diagonal(Top Right to bottom left)
for(int i = rowLen - 1; i >= 0; i--){
System.out.println(matrix[i][i]);
if(matrix[i][i] != chars[charPoint]){
charPoint = 0;
continue;
} else {
if(chars[charPoint] == chars[word.length()-1]){
return true;
}
charPoint++;
}
}
return false;
}
}
My C# solution
Console.WriteLine("Enter the no. of rows");
int r = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Enter the no. of columns");
int c = Convert.ToInt32(Console.ReadLine());
string[,] a = new string[r,c];
for(int i=0; i<r; i++)
{
for(int j=0; j<c; j++)
{
a[i,j] = Console.ReadLine();
}
}
Console.WriteLine("The characters of matrix is");
for(int i=0; i<r; i++)
{
for(int j=0; j<c; j++)
{
Console.Write("{0} ",a[i,j]);
}
Console.WriteLine();
}
Console.WriteLine("Enter a word");
string s = Console.ReadLine();
int m=0,flag=0;
for(int k=0; k<s.Length; k++)
{
for(int i=0; i<r; i++)
{
for(int j=0; j<c; j++)
{
char[] ch = a[i,j].ToCharArray();
if(s[k]==ch[m])
{
flag = 1;
break;
}
else
flag = 0;
}
if(flag==1)
break;
}
}
if(flag==1)
Console.WriteLine("True");
else
Console.WriteLine("False");
- Anonymous March 04, 2015public static boolean findWord(char[][] matrix, String word) { char[] chars = word.toCharArray(); int rowLen = matrix.length; int colLen = matrix[0].length; if (word.length() > rowLen || word.length() > colLen) { return false; } int charPoint = 0; // scan rows for (int i = 0; i < rowLen; i++) { for (int j = 0; j < colLen; j++) { if (chars[charPoint] == matrix[i][j]) { charPoint++; if (charPoint == word.length() - 1) { return true; } } else { charPoint = 0; } } } // scan cols charPoint = 0; for (int j = 0; j < colLen; j++) { for (int i = 0; i < rowLen; i++) { if (chars[charPoint] == matrix[i][j]) { charPoint++; if (charPoint == word.length() - 1) { return true; } } else { charPoint = 0; } } } // scan diagonal charPoint = 0; for (int i = 0; i < rowLen; i++) { if (chars[charPoint] == matrix[i][i]) { charPoint++; if (charPoint == word.length() - 1) { return true; } } else { charPoint = 0; } } return false; }