Word Search I
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example
Given board =
[
"ABCE",
"SFCS",
"ADEE"
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == || board[].length == ) return false;
if (word.length() == ) return true;
int rows = board.length, cols = board[].length;
boolean[][] visited = new boolean[rows][cols];
for (int i = ; i < rows; i++) {
for (int j = ; j < cols; j++) {
if (helper(board, i, j, word, , visited)) return true;
}
}
return false;
}
public boolean helper(char[][] board, int i, int j, String word, int index, boolean[][] visited) {
if (index == word.length()) return true;
if (i < || i >= board.length || j < || j >= board[].length) return false;
if (board[i][j] != word.charAt(index) || visited[i][j] == true) return false;
visited[i][j] = true;
int[][] dir = {{, }, {, -}, {, }, {-, }};
for (int row = ; row < dir.length; row++) {
int new_row = i + dir[row][];
int new_col = j + dir[row][];
if (helper(board, new_row, new_col, word, index + , visited)) {
return true;
}
}
visited[i][j] = false;
return false;
}
}
Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Return ["eat","oath"].
方法一：
把每个点作为起始点，然后朝四个方向遍历，从起始点到当前点组成的字符串如果在trie中能够找到，继续，否则，退出。
第二种方法：
把每个TrieNode放入递归方法中，如果当前字符和TrieNode的字符一致，我们再把TrieNode的每个子节点作为递归节点继续，否则退出。
public class Solution {
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
Set<String> set = new HashSet<>();
int m = board.length, n = board[].length;
boolean[][] visited = new boolean[m][n];
for (int i = ; i < m; i++) {
for (int j = ; j < n; j++) {
dfs(board, visited, i, j, trie.root.map.get(board[i][j]), new StringBuilder(), set);
}
}
return new ArrayList<String>(set);
}
public void dfs(char[][] board, boolean[][] visited, int i, int j, TrieNode node, StringBuilder sb, Set<String> set) {
int m = board.length, n = board[].length;
if (node == null || i < || j < || i >= m || j >= n || visited[i][j]) return;
if (board[i][j] != node.ch) return;
sb.append(node.ch);
if (node.isEnd) {
set.add(sb.toString());
}
visited[i][j] = true;
for (TrieNode curr : node.map.values()) {
dfs(board, visited, i - , j, curr, sb, set);
dfs(board, visited, i + , j, curr, sb, set);
dfs(board, visited, i, j - , curr, sb, set);
dfs(board, visited, i, j + , curr, sb, set);
}
visited[i][j] = false;
sb.deleteCharAt(sb.length() - );
}
}
class TrieNode {
char ch;
boolean isEnd;
Map<Character, TrieNode> map;
public TrieNode(char ch) {
this.ch = ch;
map = new HashMap<Character, TrieNode>();
}
public TrieNode getChildNode(char ch) {
return map.get(ch);
}
}
// Trie
class Trie {
public TrieNode root = new TrieNode(' ');
public void insert(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
TrieNode child = current.getChildNode(c);
if (child == null) {
child = new TrieNode(c);
current.map.put(c, child);
}
current = child;
}
current.isEnd = true;
}
}
参考请注明出处：cnblogs.com/beiyeqingteng/