212. Word Search II (Hard)
https://leetcode.com/problems/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.
Example:
Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words =["oath","pea","eat","rain"]
Output:["eat","oath"]
Note:
- All inputs are consist of lowercase letters
a-z
. - The values of
words
are distinct.
Solutions
class Solution {
private final int[] R = new int[]{0, 0, 1, -1};
private final int[] C = new int[]{1, -1, 0, 0};
private boolean[][] visited;
private Set<String> ansSet = new HashSet<>();
private Trie trie = new Trie();
private Set<String> dict = new HashSet<>();
public List<String> findWords(char[][] board, String[] words) {
for (String w : words) {
trie.insert(w);
dict.add(w);
}
int row = board.length;
int col = board[0].length;
visited = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
dfs(i, j, board, trie, board[i][j] + "");
}
}
return new ArrayList<>(ansSet);
}
private void dfs(int r, int c, char[][] board, Trie trie, String s) {
int row = board.length;
int col = board[0].length;
char newChar = board[r][c];
Trie subTrie = trie.next(newChar);
// optimization measure, means no words start with this subTrie,
// roll back to prune this branch
if (subTrie == null) {
return;
}
visited[r][c] = true;
// String s is in the candidate list for searching
// But not return here since some other words may be prefixed with s
if (dict.contains(s)) {
ansSet.add(s);
}
for (int i = 0; i < 4; i++) {
int newR = r + R[i];
int newC = c + C[i];
if (newR < 0 || newC < 0 || newR >= row || newC >= col) {
continue;
}
if (!visited[newR][newC]) {
dfs(newR, newC, board, subTrie, s + board[newR][newC]);
}
}
visited[r][c] = false;
}
// IMPORTANT, recite the structure of Trie
private class Trie {
private Map<Character, Trie> map = new HashMap<>();
public void insert(String word) {
if (word == null) {
return;
}
add(0, word);
}
private void add(int i, String word) {
if (i >= word.length()) {
map.put(null, new Trie()); //use null to indicate end of string
return;
}
char c = word.charAt(i);
Trie subTrie = map.get(c);
if (subTrie == null) {
subTrie = new Trie();
map.put(c, subTrie);
}
subTrie.add(i + 1, word);
}
public Trie next(char c) {
return this.map.get(c);
}
}
}