CareerCup

I don't know for sure. But I have some vague feeling that variable length trie would do the task. Like start for each row scan character by character and traverse the nodes and then if the prefix is a word then it will be found in a leaf and so on.

Generate(string word)
{
if(isWord(word))
print word;

for(int i =0; i< N; i++)
{
for(int j=0; j<N; J++)
{
if(IsPrefix(word, a[i][j])
Generate(word + a[i][j]);
}
}


word = string.empty ;
for(int i =0; i< N; i++)
{
for(int j=0; j<N; J++)
{
if(i==j==0) continue;
Generate(word + a[i][j]);
}
}


}


Generate (a[0][0]);

void printWord(string str, int row, int col)
{
if (isWord(str))
{
print str;
}

char nextLetter = '';
if (col < N-1){
nextLetter = a[row][++col];
}else if (row < N-1) {
col = 0;
nextLetter = a[++row][col];
}

if (nextLetter == '')
{
return;
}

str += nextLetter;
if (isPrefix(str)) {
printWord(str, row, col);
}
}


void main(...)
{

for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
{
printWord(a[i][j], i, j);
}
}

}

public static void printWord(char[][] a, String str, boolean[][] flags) {
if (isWord(str)) {
System.out.println(str);
}

if (!isPrefix(str)) {
return;
}

char nextLetter = ' ';

for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if (!flags[i][j]) {
nextLetter = a[i][j];
flags[i][j] = true;
printWord(a, str + nextLetter, t, flags);
flags[i][j] = false;
}
}
}
}

public static void main(String[] args) {
// initialization
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
flags[i][j] = true;
printWord(a, a[i][j] + "", flags);
flags[i][j] = false;
}
}
}