Word Search II
给一个2d数组, 里面是字符, 然后一个一个字符串数组, 里面是要找的字符串, 问那些能用2d数组里的字符拼起来. 这个题是最常考的题, 如果能直接用Trie还可以, 如果不能…..面试怕是直接挂了. 题目本身就是Trie的基础应用.
public class Solution {
Set<String> res = new HashSet<String>();
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dfs(board, visited, "", i, j, trie);
}
}
return new ArrayList<String>(res);
}
public void dfs(char[][] board, boolean[][] visited, String str, int x, int y, Trie trie) {
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
if (visited[x][y]) return;
str += board[x][y];
if (!trie.startsWith(str)) return;
if (trie.search(str)) {
res.add(str);
}
visited[x][y] = true;
dfs(board, visited, str, x - 1, y, trie);
dfs(board, visited, str, x + 1, y, trie);
dfs(board, visited, str, x, y - 1, trie);
dfs(board, visited, str, x, y + 1, trie);
visited[x][y] = false;
}
class TrieNode {
public boolean endPoint;
public TrieNode[] next;
public TrieNode() {
endPoint = false;
next = new TrieNode[26];
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
if(word != null) {
TrieNode tmp = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(tmp.next[c-'a'] == null)
tmp.next[c-'a'] = new TrieNode();
tmp = tmp.next[c-'a'];
}
tmp.endPoint = true;
}
}
// Returns if the word is in the trie.
public boolean search(String word) {
if(word == null)
return false;
TrieNode tmp = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(tmp.next[c-'a'] == null)
return false;
else
tmp = tmp.next[c-'a'];
}
return tmp.endPoint;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if(prefix == null)
return false;
TrieNode tmp = root;
for(int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if(tmp.next[c-'a'] == null)
return false;
else
tmp = tmp.next[c-'a'];
}
return true;
}
}
}