In my preparation for google interview, I thought I should go over some problem in career cup and I found this crossword problem pretty interesting. In my mock interview yesterday I later found a simpler solution using an intuitive recursion, so I thought I should try this problem.
The problem statement is:
Given a puzzle of letters/ characters e.g.
a e r o p s
b h a r l s
w r i s l o
a s n k t q
Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.
e.g. rain and slow will return true. rain is present in the second column and slow in the third row wrapped around.
This problem reminded me of maze exploration which can be done recursively and I started coding in that mode.
- First I would have a main recursive function which checks if the first word matches
private boolean stringFinder(char[][] ar, String str) {
int size=ar.length;
if(str.length()>size+1) return false;
int k=0;
char[] charArray=str.toCharArray();
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
if(ar[i][j]==charArray[k])
- If matches recursively check all the four directions
return isMatch(ar,charArray,i,((j+1)%size),k+1)||
isMatch(ar,charArray,((i+1)%size),j,k+1)||
isMatch(ar,charArray,((i-1)%size),j,k+1)||
isMatch(ar,charArray,i,((j-1)%size),k+1);
- In each of the directions again search for a match. (this is wrong)
private boolean isMatch(char[][] ar, char[] charArray, int i, int j, int k, Direction dir) {
int size=ar.length;
if(k==charArray.length-1)
{
if(ar[i][j]==charArray[k]) return true;
else return false;
}
if(ar[i][j]==charArray[k])
return isMatch(ar,charArray,i,((j+1)%size),k+1)||
isMatch(ar,charArray,((i+1)%size),j,k+1)||
isMatch(ar,charArray,((i-1)%size),j,k+1)||
isMatch(ar,charArray,i,((j-1)%size),k+1);
}
return false;
}
I verified this approach and it was working with pen and paper. So I opened up eclipse with a jolly mood and though I am a genius.
But there were several mistakes
- When the inevitable happened- the program is not responding as expected, I found that I am searching in all direction after I found a direction. So I modified my approach to include a direction enum.
- And tried to change i and j values based only on the direction. This time I got the directions wrong and it took a while to overcome it.
- Then I got the problem of comparing next recursion when I wanted to be in the current one. So I changed the order.
- Finally I got the result when I send in "rain" and the output is true ! And then I again checked for "slow" and magic it returned true!!
- But when I am sending in a string that does not exist I am getting an exception. Reason: I am sending in negative indexes.. Even though I am wrapping i and j values I forgot to take of –ve signs.
So finally my code became like this
package com.code.prolificcoder;
public class StringFinder {
enum Direction{up,down,left,right};
public static void main(String args[]){
char[][] ar=new char[][]{{'m','s','s','h'},
{'a','t','c','i'},
{'p','d','a','n'},
{'s','a','t','h'},
};
String str="tcia";
StringFinder sf=new StringFinder();
System.out.print(sf.stringFinder(ar,str));
}
private boolean stringFinder(char[][] ar, String str) {
int size=ar.length;
if(str.length()>size+1) return false;
int k=0;
char[] charArray=str.toCharArray();
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
if(ar[i][j]==charArray[k])
return isMatch(ar,charArray,i,Math.abs((j+1)%size),k+1,Direction.right)||
isMatch(ar,charArray,Math.abs((i+1)%size),j,k+1,Direction.down)||
isMatch(ar,charArray,Math.abs((i-1)%size),j,k+1,Direction.up)||
isMatch(ar,charArray,i,Math.abs((j-1)%size),k+1,Direction.left);
return false;
}
private boolean isMatch(char[][] ar, char[] charArray, int i, int j, int k, Direction dir) {
int size=ar.length;
if(k==charArray.length-1)
{
if(ar[i][j]==charArray[k]) return true;
else return false;
}
if(ar[i][j]==charArray[k]){
if(dir==Direction.down)
i=Math.abs((i+1)%size);
else if(dir==Direction.right)
j=Math.abs((j+1)%size);
else if(dir==Direction.left)
j=Math.abs((j-1)%size);
else //dir==Direction.up
i=Math.abs((i-1)%size);
return isMatch(ar,charArray,i,j,k+1,dir);
}
return false;
}
}
It took me more than 2 hours to get this version, in an interview you are not given this many chances and a compiler and a debugger. I should be able to correct my bugs in walkthroughs, all in all scary.
Update: My tester wife found another bug in this code. Whenever there is a search for a char that is present twice I am returning the result of the first one which could be false but the later could be true.
For eg: "scat" in the above it will return false because the first match for s resulted in false and I returned it. To solve this I update the code as follows.
private
boolean stringFinder(char[][] ar, String str) {
int size=ar.length;
if(str.length()>size+1) return
false;
int k=0;
boolean found=false;
char[] charArray=str.toCharArray();
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
if(ar[i][j]==charArray[k])
found= isMatch(ar,charArray,i,Math.abs((j+1)%size),k+1,Direction.right)||
isMatch(ar,charArray,Math.abs((i+1)%size),j,k+1,Direction.down)||
isMatch(ar,charArray,Math.abs((i-1)%size),j,k+1,Direction.up)||
isMatch(ar,charArray,i,Math.abs((j-1)%size),k+1,Direction.left)||found;
return found;
}
