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 =
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"].
Note:
You may assume that all inputs are consist of lowercase letters
You may assume that all inputs are consist of lowercase letters
a-z.
You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.
A time limit exceed solution:Use a trie to save the word which does not in the board. So each time for a new word, we first search if the prefix exist in the trie. If yes, no need to search the board again.
Simply put, the trie stores the prefix which does not exist in the board, so we don't need to waste of time to search again and again.
Code (Java):
public class Solution {
private int rows;
private int cols;
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<String>();
if (board == null || board.length == 0 || words == null || words.length == 0) {
return result;
}
Set<String> set = new HashSet<String>();
Trie trie = new Trie();
this.rows = board.length;
this.cols = board[0].length;
for (String word : words) {
if (trie.searchPrefix(word) == false) {
if (searchBoard(board, word)) {
if (!set.contains(word)) {
set.add(word);
}
} else {
trie.insert(word);
}
} else {
trie.insert(word);
}
}
return new ArrayList<String>(set);
}
private boolean searchBoard(char[][] board, String word) {
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (searchBoardHelper(board, i, j, word, 0, visited)) {
return true;
}
}
}
return false;
}
private boolean searchBoardHelper(char[][] board, int row, int col, String word, int index, boolean[][] visited) {
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return false;
}
if (visited[row][col]) {
return false;
}
if (board[row][col] != word.charAt(index)) {
return false;
}
visited[row][col] = true;
if (index == word.length() - 1 && board[row][col] == word.charAt(index)) {
return true;
}
boolean ret;
ret = searchBoardHelper(board, row - 1, col, word, index + 1, visited) ||
searchBoardHelper(board, row + 1, col, word, index + 1, visited) ||
searchBoardHelper(board, row, col - 1, word, index + 1, visited) ||
searchBoardHelper(board, row, col + 1, word, index + 1, visited);
visited[row][col] = false;
return ret;
}
class Trie {
private TrieNode root = new TrieNode();
// Insert a word
void insert(String s) {
TrieNode curr = root;
int offset = 'a';
for (int i = 0; i < s.length(); i++) {
char character = s.charAt(i);
if (curr.children[character - offset] == null) {
curr.children[character - offset] =
new TrieNode(character, i == s.length() - 1 ? true : false);
} else {
if (i == s.length() - 1) {
curr.children[character - offset].leaf = true;
}
}
curr = curr.children[character - offset];
}
}
// Search for prefix
boolean searchPrefix(String s) {
TrieNode curr = root;
int offset = 'a';
for (int i = 0; i < s.length(); i++) {
char character = s.charAt(i);
if (curr.children[character - offset] == null) {
return false;
} else if (curr.children[character - offset] != null && curr.children[character - offset].leaf) {
return true;
}
curr = curr.children[character - offset];
}
return false;
}
}
class TrieNode {
char val;
boolean leaf;
TrieNode[] children;
public TrieNode() {
this.val = '\0';
this.children = new TrieNode[26];
}
public TrieNode(char val, boolean leaf) {
this.val = val;
this.leaf = leaf;
this.children = new TrieNode[26];
}
}
}
Code (Java):
public class Solution {
private int rows;
private int cols;
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<String>();
if (board == null || board.length == 0 || words == null || words.length == 0) {
return result;
}
Set<String> set = new HashSet<String>();
Trie trie = new Trie();
this.rows = board.length;
this.cols = board[0].length;
// Step 1: insert all words into a trie
for (String word : words) {
trie.insert(word);
}
// Step 2: search the board
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
searchBoardHelper(board, i, j, "", visited, trie, set);
}
}
return new ArrayList<String>(set);
}
private void searchBoardHelper(char[][] board, int row, int col, String word,
boolean[][] visited, Trie trie, Set<String> set) {
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return;
}
if (visited[row][col]) {
return;
}
word += board[row][col];
if (!trie.searchPrefix(word)) {
return;
}
if (trie.search(word)) {
set.add(word);
}
visited[row][col] = true;
searchBoardHelper(board, row - 1, col, word, visited, trie, set);
searchBoardHelper(board, row + 1, col, word, visited, trie, set);
searchBoardHelper(board, row, col - 1, word, visited, trie, set);
searchBoardHelper(board, row, col + 1, word, visited, trie, set);
visited[row][col] = false;
}
class Trie {
private TrieNode root = new TrieNode();
// Insert a word
void insert(String s) {
TrieNode curr = root;
int offset = 'a';
for (int i = 0; i < s.length(); i++) {
char character = s.charAt(i);
if (curr.children[character - offset] == null) {
curr.children[character - offset] =
new TrieNode(character, i == s.length() - 1 ? true : false);
} else {
if (i == s.length() - 1) {
curr.children[character - offset].leaf = true;
}
}
curr = curr.children[character - offset];
}
}
// Search a word
boolean search(String s) {
TrieNode curr = root;
int offset = 'a';
for (int i = 0; i < s.length(); i++) {
char character = s.charAt(i);
if (curr.children[character - offset] == null) {
return false;
}
curr = curr.children[character - offset];
}
if (curr != null && !curr.leaf) {
return false;
}
return true;
}
// Search for prefix
boolean searchPrefix(String s) {
TrieNode curr = root;
int offset = 'a';
for (int i = 0; i < s.length(); i++) {
char character = s.charAt(i);
if (curr.children[character - offset] == null) {
return false;
}
curr = curr.children[character - offset];
}
return true;
}
}
class TrieNode {
char val;
boolean leaf;
TrieNode[] children;
public TrieNode() {
this.val = '\0';
this.children = new TrieNode[26];
}
public TrieNode(char val, boolean leaf) {
this.val = val;
this.leaf = leaf;
this.children = new TrieNode[26];
}
}
}
Analysis:
Let's think about the naive solution first. The naive solution is we search the board for each board. So for the dict with n words, and assume the ave. length of each word has length of m. Then without using a Trie, the time complexity would be O(n * rows * cols * 4^m).
Now let's analyze the time complexity of using a Trie. We put each word into the trie. Search in the Trie takes O(m) time, so the time complexity would be O(rows * cols * m * 4^m). Since mostly m << n, using a trie would save lots of time.
A better solution:
The key observation with the previous solution is we don't need to search the trie for each prefix from the root; Instead, we can keep track of the current pointer to the trie. The time complexity is O(rows * cols * 4^m).
Code (Java):
public class Solution {
/**
* @param board: A list of lists of character
* @param words: A list of string
* @return: A list of string
*/
public List<String> wordSearchII(char[][] board, List<String> words) {
List<String> ans = new ArrayList<>();
if (board == null || board[0] == null || words == null) {
return ans;
}
Set<String> set = new HashSet<>();
boolean[][] visited = new boolean[board.length][board[0].length];
// step 1: create a trie and put words into the trie
//
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
// step 2: scan the board and check if the word in the trie
//
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
wordSearchHelper(i, j, board, visited, set, trie.root);
}
}
return new ArrayList<>(set);
}
private void wordSearchHelper(int row, int col, char[][] board, boolean[][] visited, Set<String> set, TrieNode p) {
int m = board.length;
int n = board[0].length;
if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col]) {
return;
}
char c = board[row][col];
if (p.children[c - 'a'] == null) {
return;
}
visited[row][col] = true;
p = p.children[c - 'a'];
if (!p.word.isEmpty()) {
set.add(p.word);
}
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < 4; i++) {
wordSearchHelper(row + dirs[i][0], col + dirs[i][1], board, visited, set, p);
}
visited[row][col] = false;
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
if (p.children[c - 'a'] == null) {
p.children[c - 'a'] = new TrieNode();
}
p = p.children[c - 'a'];
}
p.word = word;
}
}
class TrieNode {
TrieNode[] children;
String word;
public TrieNode() {
children = new TrieNode[26];
word = "";
}
}
public class Solution {
/**
* @param board: A list of lists of character
* @param words: A list of string
* @return: A list of string
*/
public List<String> wordSearchII(char[][] board, List<String> words) {
// write your code here
List<String> res = new ArrayList<>();
if (board == null || board.length == 0 || words == null || words.size() == 0) {
return res;
}
Trie trie = new Trie();
for (String word : words) {
trie.addWord(word);
}
int nRows = board.length;
int nCols = board[0].length;
Set<String> set = new HashSet<>();
for (int i = 0; i < nRows; i++) {
for (int j = 0; j < nCols; j++) {
TrieNode p = trie.root;
boolean[][] visited = new boolean[nRows][nCols];
if (p.children[board[i][j] - 'a'] != null) {
search(i, j, board, visited, p.children[board[i][j] - 'a'], set);
}
}
}
return new ArrayList<>(set);
}
private void search(int row, int col, char[][] board, boolean[][] visited, TrieNode p, Set<String> res) {
//char c = board[row][col];
if (p == null) {
return;
}
if (p.word != null) {
res.add(p.word);
}
int[][] dirs = {{-1 ,0}, {1, 0}, {0, -1}, {0, 1}};
int nRows = board.length;
int nCols = board[0].length;
visited[row][col] = true;
for (int[] dir : dirs) {
int nextRow = row + dir[0];
int nextCol = col + dir[1];
if (nextRow >= 0 && nextRow < nRows && nextCol >= 0 && nextCol < nCols && !visited[nextRow][nextCol]) {
search(nextRow, nextCol, board, visited, p.children[board[nextRow][nextCol] - 'a'], res);
}
}
visited[row][col] = false;
}
}
class TrieNode {
TrieNode[] children;
String word;
public TrieNode() {
this.children = new TrieNode[26];
word = null;
}
}
class Trie {
public TrieNode root;
public Trie() {
this.root = new TrieNode();
}
public void addWord(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
if (p.children[c - 'a'] == null) {
p.children[c - 'a'] = new TrieNode();
}
p = p.children[c - 'a'];
}
p.word = word;
}
}
Could you please explain the complexity part?
ReplyDelete