My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
private class TrieNode {
TrieNode[] next = new TrieNode[26];
char val;
boolean isWord;
TrieNode(char val) {
this.val = val;
}
}
private TrieNode root = new TrieNode('r');
int row = 0;
int col = 0;
private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public List<String> findWords(char[][] board, String[] words) {
List<String> ret = new ArrayList<String>();
if (board == null || board.length == 0 || board[0].length == 0) {
return ret;
}
row = board.length;
col = board[0].length;
buildTrie(words);
boolean[][] mark = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
dfs(i, j, mark, root, new StringBuilder(), ret, board);
}
}
return ret;
}
private void dfs(int i, int j, boolean[][] mark, TrieNode root, StringBuilder path, List<String> ret, char[][] board) {
int index = (int) (board[i][j] - 'a');
if (root.next[index] == null) { // not match
return;
}
int len = path.length();
path.append(board[i][j]);
mark[i][j] = true;
TrieNode curr = root.next[index];
if (curr.isWord) {
ret.add(path.toString());
curr.isWord = false; // cannot be found again
}
for (int k = 0; k < dir.length; k++) {
int next_r = i + dir[k][0];
int next_c = j + dir[k][1];
if (isValid(next_r, next_c) && !mark[next_r][next_c]) {
dfs(next_r, next_c, mark, curr, path, ret, board);
}
}
path.setLength(len);
mark[i][j] = false;
}
private boolean isValid(int i, int j) {
if (i < 0 || i >= row) {
return false;
}
else if (j < 0 || j>= col) {
return false;
}
else {
return true;
}
}
private void buildTrie(String[] words) {
for (String word : words) {
buildTrie(word, 0, root);
}
}
private void buildTrie(String s, int index, TrieNode root) {
if (index >= s.length()) {
root.isWord = true;
return;
}
int offset = (int) (s.charAt(index) - 'a');
if (root.next[offset] == null) {
root.next[offset] = new TrieNode(s.charAt(index));
}
TrieNode curr = root.next[offset];
buildTrie(s, index + 1, curr);
}
public static void main(String[] args) {
Solution test = new Solution();
char[][] board = new char[][]{{'o','a','a','n'}, {'e','t','a','e'}, {'i','h','k','r'}, {'i','f','l','v'}};
String[] words = new String[]{"oath","pea","eat","rain"};
List<String> ret = test.findWords(board, words);
System.out.println(ret.toString());
}
}
reference:
https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00
这道题目没能做出来，但真的很有意思。也给做难题提供了一些思路。
什么思路？当你对一道题目无从下手的时候，是为什么？
难道你真的一点都不会做吗？一个解法都没有吗？
不是。你有你的暴力解法，但是觉得复杂度太高，太可笑了。不可能是最优解。
当然不是最优解。但大多数最优解都不可能一下子想到的。
大多数最优解都是从 brute-force 优化出来的。
这道题目也是。
我当时在想，如果把 word search I 作为子函数，把输入的string都过一遍，不就完事了吗？但我没有这么写。为什么？
因为我知道太蠢了，过不了测试的。
那为什么过不了测试？
因为复杂度太高。
为什么复杂度高？
因为每个string都得做一次搜索操作，其实很多string有相同的prefix,可以放在一起搜索。也可以及时的截止
也就是说，我们在搜索 board[][]的时候，不是像 I 里面一样，盲目的瞎搜索，而是得按照 words[] 定义的路径去搜索。这样，
才能更快地找到目标string
才能更快地发现，继续下去，已经不可能有word 与他匹配。
注意这里，如果用普通的搜索，当我们到达一个结点，判断是否可以继续dfs的时候，需要遍历words[],看看是否有匹配的。复杂度就是
O(n), 每次搜索都是如此，复杂度惊人。所以，我们需要O(1)
那么我们的目标就是：
1 . 有方向性的去搜索
2 . 知道当前的character是否有匹配的word,要求操作是 瞬时的
再总结：
就是，我们需要知道，何时，已经没必要，再继续dfs了，瞬时。
Trie 一定是最好的结构。
下面再来思考下 backtracking
有两种形式
mark[i][j] = true;
int len = path.length();
path.append(curr);
for (int i = 0; i < n; i++) {
if (!mark[m][n]) {
dfs(...);
}
}
mark[i][j] = false;
path.setLength(len);
上面这种形式，特征是，这一层，只干这一层的事。
可以看到， mark 标志位，改变string，都是这一层自己干的事。
唯一和下一层有关的。就是dfs的时候判断下，他们是否已经被访问过了。
还有种形式
for (int i = begin; i < n; i++) {
s += s.substring(begin, i + 1);
group.add(s);
dfs(i, s, group);
group.remove(group.size() - 1);
}
这种的话，会将 backtacking 的过程在 for-loop里面实现。
之前的是在 for-loop 外面实现。
两种不同的形式。
Anyway, Good luck, Richardo! -- 09/20/2016
