## Thursday, October 4, 2012

### SRM232

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3

## Tutorials:

### Solution

Here we use Trie to track the existence of each word or prefix. Each node in nodes is a prefix or word, which is start at (row, col). Then, it could extend to next 26 possible letters. For my program, it will take a lot of space, it will take 50*50*50(row length * col length * possible max length of word) which is 125K units. So, make sure you have enough space. If you are using C++, you can open more space like 500K units.

### Source Code:

```import java.util.ArrayList;
import java.util.List;

/**
* @author: antonio081014
*/
public class WordFind {

private int N;
private int R;
private int C;
private TrieNode[] nodes;
private String[] g;

private static final int[] dx = { 1, 1, 0 };
private static final int[] dy = { 0, 1, 1 };

public void add(int n, int r, int c, int d, int rr, int cc) {
if (rr >= R || cc >= C)
return;
int rrr = rr + dx[d];
int ccc = cc + dy[d];
int ch = g[rr].charAt(cc) - 'A';
if (nodes[n].next[ch] == -1) {
nodes[n].next[ch] = N++;
nodes[N - 1].row = r;
nodes[N - 1].col = c;
add(N - 1, r, c, d, rrr, ccc);
} else {
add(nodes[n].next[ch], r, c, d, rrr, ccc);
}
}

public String[] findWords(String[] grid, String[] wordList) {
g = grid;
R = grid.length;
C = grid[0].length();
this.nodes = new TrieNode[300000];
for (int i = 0; i < 300000; i++) {
nodes[i] = new TrieNode();
// nodes[i].row = -1;
// nodes[i].col = -1;
// nodes[i].next = new int[26];
// for (int j = 0; j < 26; j++)
// nodes[i].next[j] = -1;
}
N = 1;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length(); j++) {
for (int d = 0; d < 3; d++) {
add(0, i, j, d, i, j);
}
}
}
List<String> list = new ArrayList<String>();
for (int i = 0; i < wordList.length; i++) {
int start = 0;
for (int j = 0; j < wordList[i].length(); j++) {
int c = wordList[i].charAt(j) - 'A';
if (nodes[start].next[c] == -1) {
start = -1;
break;
} else {
start = nodes[start].next[c];
}
}
if (start == -1)
else
list.add("" + nodes[start].row + " " + nodes[start].col);
}
return list.toArray(new String[0]);
}

}

class TrieNode {
public int row;
public int col;
public int next[];

public TrieNode() {
this.row = -1;
this.col = -1;
this.next = new int[26];
for (int i = 0; i < 26; i++)
this.next[i] = -1;
}
}
```