SRM232

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

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

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)
  list.add("");
     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;
    }
}

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Source Code:

---

Division Two - Level One:

Solution

Source Code: