Question 2 World Search I& II
Method 1 DFS 3 all path
High level
traverse all paths of the graph
find a path that matches the target words
Middle Level
each level:
check current character if it matches the latter
if match, go next character
level by level
static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static List<String> findWordsBruteForce(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
for (String word: words) {
if (exist(board, word))) {
res.add(word);
}
}
return res;
}
private static boolean exist(char[][] board, String word) {
boolean[][] visited = new boolean[rows][cols];
for (int i = 0 ; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (helper(board, i, j , word, 0, visited)) {
return true;
}
}
}
return false;
}
private static boolean helper(char[][] board, int x, int y, String word, int index, boolean[][] visited) {
// basic case
if (index == word.length()) {
return true;
}
//if (visited[x][y]) {
// return false;
//}
visited[x][y] = true;
for (int[] dir: DIRS) {
int neiX = dir[0] + x;
int neiY = dir[1] + y;
if (valid(neiX, neiY, board) && visited[neiX][neiY]) {
if (helper(board, neiX, neiY, word, index + 1, visited)) {
return true;
}
}
}
visited[x][y] = false;
return false;
}
private boolean isValid(char[][] board, int x, int y) {
return x >=0 && x< board.length && y >=0 && y < board[0].length;
}
Method 2 Trie Tree + dfs backtracking
simplified version(word search I): What if we are only given one target word, and we are to find if the word is in the matrix?
simultaneously traverse the board, and the target word
(word search II) simultaneously traverse the board and the trie
class TrieNode {
// maps a character to its corresponding child
public Map<Character, TrieNode> children;
public boolean isWord;
public boolean add(String word) {
if (search word) {
return false;
}
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
TrieNode next = cur.children.get(word.charAt(i));
if (next == null) {
next = new TrieNode();
cur.children.put(word.charAt(i), next);
}
cur = next;
}
cur.isWord = true;
return true;
}
}
public static Set<String> findWords(char[][] board, String[] words) {
// sanity check
if (board == null || board.length == 0 || board[0].length == 0; || words == null || words.length == 0) {
throw new IllegalArgumentException("invalid input");
}
Set<String> res = new HashSet<>();
// step one --> build the Trie form the given list of words
TrieNode root = buildTrie(words);
final int rows = baord.length;
final int cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
helper(board, i, j, root, sb, res, visited);
}
}
return res;
}
private static TrieNdoe buildTrie(String[] words) {
TrieNode root = new TrieNode;
for (int i = 0; i < words.size; i++) {
root.add(words[i]);
}
return root;
}
private static void helper(char[][] board, int x, int y, TrieNode root, StringBuilder sb,
Set<String> res, boolean[][] visited) {
// visited represents visited cells on the path
// from (i, j) to (x, y) (excluding (x, y))
// base cases
if (isValid(board, x, y)) {
return;
}
if (visited[x][y]) {
return;
}
char ch = board[x][y];
if (!root.children.contains(ch)) {
return;
}
// recursive rule
root = root.children.get(ch);
sb.append(ch);
if (root.isWord) {
res.add(sb.toString());
// do not return here because of root.isWord is not a base case
}
visited[x][y] = true;
for (int[] dir: DIRS) {
int neiX = dir[0] + x;
int neiY = dir[1] + y;
helper(board, neiX, neiY, root, sb, res, visited);
}
visited[x][y] = false;
sb.deleteCharAt(sb.length() - 1);
}
private boolean isValid(char[][] board, int x, int y) {
return x >= 0 && x< board.length && y >=0 && y < board[0].length;
}
Last updated