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:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Output: ["eat","oath"]
- Method：TrieTree, dfs
class Solution {
int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<String> findWords(char[][] board, String[] words) {
for(String s : words)
insert(s);
Set<String> res = new HashSet<>();
boolean[][] used = new boolean[board.length][board[0].length];
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
dfs(board, res, new StringBuilder(), i, j, used);
}
}
return new ArrayList<String>(res);
}
private void dfs(char[][] board, Set<String> set, StringBuilder sb, int row, int col, boolean[][] used){
int height = board.length, width = board[0].length;
if(row >= 0 && row < height && col >= 0 && col < width && !used[row][col]){
sb.append(board[row][col]);
String ss = sb.toString();
if(!hasPrefix(ss)){
sb.deleteCharAt(ss.length() - 1);
return;
}
if(search(ss)) set.add(ss);
board[row][col] = true;
for(int i = 0; i < 4; i++){
dfs(board, set, sb, row + dir[i][0], col + dir[i][1], used);
}
sb.deleteCharAt(sb.toString().length() - 1);
used[row][col] = false;
}
}
private TrieNode root = new TrieNode();
private static class TrieNode{
boolean isLeaf;
TrieNode[] childs;
public TrieNode(){
childs = new TrieNode[26];
}
}
private void insert(String s){
int len = s.length();
TrieNode temp = root;
for(int i = 0; i < len; i++){
int c = s.charAt(i) - 'a';
if(temp.childs[c] == null)
temp.childs[c] = new TrieNode();
temp = temp.childs[c];
}
temp.isLeaf = true;
}
private boolean search(String word){
int len = word.length();
TrieNode temp = root;
for(int i = 0; i < len; i++){
int c = word.charAt(i) - 'a';
if(temp.childs[c] == null) return false;
temp = temp.childs[c];
}
return temp.isLeaf;
}
private boolean hasPrefix(String word){
int len = word.length();
TrieNode temp = root;
for(int i = 0; i < len; i++){
int c = word.charAt(i) - 'a';
if(temp.childs[c] == null) return false;
temp = temp.childs[c];
}
return true;
}
}- Use DFS to find all words, super slow.
class Solution {
private int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new LinkedList<>();
if(words == null || words.length == 0) return result;
int height = board.length, width = board[0].length;
boolean[][] visited = null;
Set<String> set = new HashSet<>();
LABEL:
for(String word : words){
if(set.contains(word)) continue;
set.add(word);
visited = new boolean[height][width];
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
char c = word.charAt(0);
if(c == board[i][j]){
visited[i][j] = true;
if(dfs(board, word, 1, height, width, i, j, visited, result))
continue LABEL;
visited[i][j] = false;
}
}
}
}
return result;
}
private boolean dfs(char[][] board, String word, int index, int height, int width, int x, int y, boolean[][] visited, List<String> result){
if(index == word.length()){
result.add(word);
return true;
}else{
int tempX, tempY;
char c = word.charAt(index);
for(int i = 0; i < 4; i++){
tempX = x + dir[i][0];
tempY = y + dir[i][1];
if(check(board, visited, height, width, tempX, tempY, c)){
visited[tempX][tempY] = true;
if(dfs(board, word, index + 1, height, width, tempX, tempY, visited, result)){
return true;
}
visited[tempX][tempY] = false;
}
}
return false;
}
}
private boolean check(char[][] board, boolean[][] visited, int height, int width, int x, int y, char c){
if(x >= 0 && x < height && y >= 0 && y < width && !visited[x][y] && c == board[x][y]){
return true;
}
return false;
}
}class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
if(words == null || words.length == 0) return result;
int height = board.length, width = board[0].length;
boolean[][] visited = new boolean[height][width];
Set<String> set = new HashSet<>();
for(String word: words){
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
if(board[i][j] == word.charAt(0)){
visited[i][j] = true;
dfs(board, set, word, i, j, 0, new boolean[height][width]);
visited[i][j] = false;
}
}
}
}
result.addAll(set);
return result;
}
private void dfs(char[][] board, Set<String> result, String word, int i, int j, int index, boolean[][] visited){
if(index == word.length() - 1){
result.add(word);
}else{
visited[i][j] = true;
int tempRow = 0, tempCol = 0;
for(int d = 0; d < 4; d++){
tempRow = i + dir[d][0];
tempCol = j + dir[d][1];
if(tempRow >= 0 && tempRow < visited.length && tempCol >= 0 && tempCol < visited[0].length && !visited[tempRow][tempCol] && board[tempRow][tempCol] == word.charAt(index + 1))
dfs(board, result, word, tempRow, tempCol, index + 1, visited);
}
visited[i][j] = false;
}
}
}- Method 1: dfs
class Solution { private char[][] board; private int height, width; private static final int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public List<String> findWords(char[][] board, String[] words) { List<String> result = new ArrayList<>(); if(board == null || board.length == 0 || board[0].length == 0) return result; this.board = board; this.height = board.length; this.width = board[0].length; LABEL: for(String word: words){ for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(word.charAt(0) == board[i][j]){ Set<Integer> visited = new HashSet<>(); visited.add(i * width + j); if(dfs(i, j, word, 1, visited)){ result.add(word); continue LABEL; } } } } } return result; } private boolean dfs(int x, int y, String word, int index, Set<Integer> visited){ if(index == word.length()) return true; else if(index < word.length()){ int tx = 0, ty = 0; for(int d = 0; d < 4; d++){ tx = x + dir[d][0]; ty = y + dir[d][1]; if(tx >= 0 && tx < height && ty >= 0 && ty < width && !visited.contains(tx * width + ty) && board[tx][ty] == word.charAt(index)){ visited.add(tx * width + ty); if(dfs(tx, ty, word, index + 1, visited)) return true; visited.remove(tx * width + ty); } } } return false; } }
- Method 1: dfs
class Solution {
private:
vector<string> res_;
static int dir[4][2];
vector<vector<char>> board_;
int height_, width_;
bool dfs(int index, const string& word, int row, int col){
if(index == word.length()) return true;
int tx = 0, ty = 0;
for(int d = 0; d < 4; ++d){
tx = row + Solution::dir[d][0];
ty = col + Solution::dir[d][1];
if(tx >= 0 && tx < height_ && ty >= 0 && ty < width_ && board_[tx][ty] != '#' && board_[tx][ty] == word[index]){
char c = board_[tx][ty];
board_[tx][ty] = '#';
if(dfs(index + 1, word, tx, ty)){
board_[tx][ty] = c;
return true;
}
board_[tx][ty] = c;
}
}
return false;
}
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
height_= board.size();
width_ = board[0].size();
board_ = move(board);
unordered_set<string> set(words.begin(), words.end());
for(const string& word: set){
bool found = false;
for(int i = 0; i < height_ && !found; ++i){
for(int j = 0; j < width_ && !found; ++j){
if(word[0] == board_[i][j]){
char c = board_[i][j];
board_[i][j] = '#';
if(dfs(1, word, i, j)){
res_.emplace_back(word);
found = true;
}
board_[i][j] = c;
}
}
}
}
return res_;
}
};
int Solution::dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static auto speedup=[](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return nullptr;
}();- Method 2: Tire Tree
struct Node{
vector<Node*> childs;
const string* word;
Node(): childs(26), word(nullptr){}
~Node(){
for(auto node: childs){
delete node;
}
}
};
class Solution {
private:
unique_ptr<Node> root_;
void insert(const string& word){
Node* temp = root_.get();
for(const char& c: word){
if(!temp->childs[c - 'a']){
temp->childs[c - 'a'] = new Node();
}
temp = temp->childs[c - 'a'];
}
temp->word = &word;
}
static int dir[4][2];
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
root_.reset(new Node());
for(const string& word: words){
insert(word);
}
int height = board.size(), width = board[0].size();
vector<string> res;
function<void(int, int, Node*)> walk = [&](int i, int j, Node* node){
if(i < 0 || i >= height || j < 0 || j >= width || board[i][j] == '#') return;
const char c = board[i][j];
Node* next = node->childs[c - 'a'];
if(!next) return;
if(next->word){
res.emplace_back(*next->word);
next->word = nullptr;
}
int tx = 0, ty = 0;
board[i][j] = '#';
for(int d = 0; d < 4; ++d){
tx = i + dir[d][0];
ty = j + dir[d][1];
walk(tx, ty, next);
}
board[i][j] = c;
};
for(int i = 0; i < height; ++i){
for(int j = 0; j < width; ++j){
walk(i, j, root_.get());
}
}
return res;
}
};
int Solution::dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static auto speedup=[](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return nullptr;
}();