Amazon Interview Question Applications Developers
Country: India
I thought of the same solution and thought it was sufficient because I interpreted the words as being English / natural language words. That would make them all relatively short and prevent the number of possibilities, which is exponential in the word length, from getting out of hand.
can't understand why it is exponential? for each of the <i,j> pairs(N^2), we need to traverse all N^2 in worst as there are no loops allowed we will not be visiting the alphabets already visited, also characters should be adjacent(within 4 neighbors) to form word Am i wrong at anything ?.
What does is_word and is_prefix return?
If they return that word is present in dictionary then or it is a prefix of any word then that can be solved with DP.
DP is the straihght fwd approach for this problem.
public void findWords(char[][] m, int i, int j, LinkedList<char> path){
if( IsWord( path.toString + m[i][j])){
System.out.println( path.toString + m[i][j]) );
}
if ( IsPrefix( path.toString + m[i][j]) ){
path.add( m[i][j] );
if ( ! path.contains( m[i-1][j]) ){
findWords( m, i-1, j, path);
}
if ( ! path.contains( m[i+1][j]) ){
findWords( m, i+1, j, path);
}
if ( ! path.contains( m[i][j-1]) ){
findWords( m, i, j-1, path);
}
if ( ! path.contains( m[i][j+1]) ){
findWords( m, i, j+1, path);
}
// Start a new search
LinkedList<char> newPath = new LinkedList<char>();
newPath.add( m[i][j] );
findWords( m, i-1, j, newPath);
findWords( m, i+1, j, newPath);
findWords( m, i1, j-1, newPath);
findWords( m, i, j+1, newPath);
}
I can only see exponential solution for this
- loveCoding July 12, 2012below is explanation
1) For <i,j>, there are 4 possibilities <i-1,j>,<i+1,j>,<i,j-1>,<i,j+1>
2) Maintain a set for already traversed Pairs, If that alreadu exit dont explore that path
3) Now for each possiblity check if its word print the word and continue, If not word check if it is prefix, if thats true then continue else we ignore that path.