212. Word Search II

  • 22.8%

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.

1
2
3
4
5
6
7
8
9
10
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"].

Note:

You may assume that all inputs are consist of lowercase letters a-z.


https://discuss.leetcode.com/topic/14301/my-c-trie-backtrace-based-solution-48-ms

My C++ Trie + Backtrace based solution (48 ms)

The idea is to use a Trie to build a prefix tree for words to simplify the search and do DFS to search all the possible strings.

For Trie, 26 pointers to point the sub-strings and a bool leaf to indicate whether the current node is a leaf (i.e. a string in words) and also idx is used to save the index of words for the current node.

For DFS, just check if the current position is visited before (board[i][j]==’X’), if so, return, check if there is a string with such prefix (nullptr == root->children[words[idx][pos]-‘a’]), if not, return; otherwise, check if the current searched string is a leaf of the trie (a string in words), if so, save it to res and set leaf of the trie node to false to indicate such string is already found. At last, move to its neighbors to continue the search. Remember to recover the char [i][j] at the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
class Trie{
public:
Trie *children[26]; // pointers to its substrings starting with 'a' to 'z'
bool leaf; // if the node is a leaf, or if there is a word stopping at here
int idx; // if it is a leaf, the string index of the array words
Trie()
{
this->leaf = false;
this->idx = 0;
fill_n(this->children, 26, nullptr);
}
};

public:
void insertWords(Trie *root, vector<string>& words, int idx)
{
int pos = 0, len = words[idx].size();
while(pos<len)
{
if(nullptr == root->children[words[idx][pos]-'a']) root->children[words[idx][pos]-'a'] = new Trie();
root = root->children[words[idx][pos++]-'a'];
}
root->leaf = true;
root->idx = idx;
}

Trie *buildTrie(vector<string>& words)
{
Trie *root = new Trie();
int i;
for(i=0; i<words.size();i++) insertWords(root, words, i);
return root;
}

void checkWords(vector<vector<char>>& board, int i, int j, int row, int col, Trie *root, vector<string> &res, vector<string>& words)
{
char temp;
if(board[i][j]=='X') return; // visited before;
if(nullptr == root->children[board[i][j]-'a']) return ; // no string with such prefix
else
{
temp = board[i][j];
if(root->children[temp-'a']->leaf) // if it is a leaf
{
res.push_back(words[root->children[temp-'a']->idx]);
root->children[temp-'a']->leaf = false; // set to false to indicate that we found it already
}
board[i][j]='X'; //mark the current position as visited
// check all the possible neighbors
if(i>0) checkWords(board, i-1, j, row, col, root->children[temp-'a'], res, words);
if((i+1)<row) checkWords(board, i+1, j, row, col, root->children[temp-'a'], res, words);
if(j>0) checkWords(board, i, j-1, row, col, root->children[temp-'a'], res, words);
if((j+1)<col) checkWords(board, i, j+1, row, col, root->children[temp-'a'], res, words);
board[i][j] = temp; // recover the current position
}
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
int row = board.size();
if(0==row) return res;
int col = board[0].size();
if(0==col) return res;
int wordCount = words.size();
if(0==wordCount) return res;

Trie *root = buildTrie(words);

int i,j;
for(i =0 ; i<row; i++)
{
for(j=0; j<col && wordCount > res.size(); j++)
{
checkWords(board, i, j, row, col, root, res, words);
}
}
return res;
}
};

Based on the comments received. I created another version with Trie node counter (thanks, zhiqing_xiao and gxyeecspku). However, for the current test set, it doesn’t help too much. Anyway, my version with Trie node counter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
private:
class Trie
{
public:
Trie * children[26];
bool isLeaf;
int wordIdx;
int prefixCount;

Trie()
{
isLeaf = false;
wordIdx = 0;
prefixCount = 0;
fill_n(children, 26, nullptr);
}

~Trie()
{
for(auto i=0; i<26; ++i) delete children[i];
}
};
void insertWord(Trie *root, const vector<string>& words, int idx)
{
int i, childID, len = words[idx].size();
for(i=0, root->prefixCount++ ; i<len; ++i)
{
childID = words[idx][i]-'a';
if(!root->children[childID]) root->children[childID] = new Trie();
root = root->children[childID];
++root->prefixCount;
}
root->isLeaf = true;
root->wordIdx = idx;
}

Trie *buildTrie(const vector<string> &words)
{
Trie *root = new Trie();
for(int i=0; i < words.size(); ++i) insertWord(root, words, i);
return root;
}

int dfs_Trie(vector<string> &res, Trie *root, vector<vector<char>>& board, vector<string>& words, int row, int col)
{
int detected = 0;

if(root->isLeaf)
{
++detected;
root->isLeaf = false;
res.push_back(words[root->wordIdx]);
}

if( row<0 || row>=board.size() || col<0 || col>=board[0].size() || board[row][col]=='*' || !root->children[ board[row][col]-'a'] || root->children[ board[row][col]-'a']->prefixCount <= 0 ) return detected;
int curC = board[row][col] - 'a';
board[row][col] = '*';
detected += dfs_Trie(res, root->children[curC], board, words, row-1, col) +
dfs_Trie(res, root->children[curC], board, words, row+1, col) +
dfs_Trie(res, root->children[curC], board, words, row, col - 1) +
dfs_Trie(res, root->children[curC], board, words, row, col + 1) ;
root->prefixCount -=detected;
board[row][col] = curC+'a';
return detected;
}

public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
int M, N, wordNum = words.size();
vector<string> res;
if( !(M = board.size()) || !(N = board[0].size()) || !wordNum) return res;
Trie *root = buildTrie(words);
for(auto i=0; i<M && root->prefixCount; ++i)
for(auto j=0; j<N; ++j)
dfs_Trie(res, root, board, words, i, j);
delete root;
return res;
}
};

https://discuss.leetcode.com/topic/20210/my-ac-very-clean-c-code

My AC very clean C++ code

The idea is start from every position of the board, and then see if we can find a word starting from this position with checking if is_end is true in TrieNode structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class TrieNode{
public:
bool is_end;
vector<TrieNode*> children;
TrieNode(){
is_end=false;
children=vector<TrieNode*>(26, NULL);
}
};

class Trie{
public:
TrieNode* getRoot(){return root;}
Trie(vector<string>& words){
root=new TrieNode();
for(int i=0; i<words.size(); ++i)
addWord(words[i]);
}
void addWord(const string& word){
TrieNode* cur=root;
for(int i=0; i<word.size(); ++i){
int index=word[i]-'a';
if(cur->children[index]==NULL)
cur->children[index]=new TrieNode();
cur=cur->children[index];
}
cur->is_end=true;
}
private:
TrieNode* root;
};

class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
Trie* trie = new Trie(words);
TrieNode* root=trie->getRoot();
set<string> result_set;
for(int x=0; x<board.size(); ++x)
for(int y=0; y<board[0].size(); ++y)
findWords(board, x, y, root, "", result_set);

vector<string> result;
for(auto it:result_set) result.push_back(it);
return result;
}
private:
void findWords(vector<vector<char>>& board, int x, int y, TrieNode* root, string word, set<string>& result){
if(x<0||x>=board.size()||y<0||y>=board[0].size() || board[x][y]==' ') return;

if(root->children[board[x][y]-'a'] != NULL){
word=word+board[x][y];
root=root->children[board[x][y]-'a'];
if(root->is_end) result.insert(word);
char c=board[x][y];
board[x][y]=' ';
findWords(board, x+1, y, root, word, result);
findWords(board, x-1, y, root, word, result);
findWords(board, x, y+1, root, word, result);
findWords(board, x, y-1, root, word, result);
board[x][y]=c;
}
}
};

https://discuss.leetcode.com/topic/14307/27-lines-uses-complex-numbers

27 lines, uses complex numbers

I first build the tree of words with root root and also represent the board a different way, namely as one-dimensional dictionary where the keys are complex numbers representing the row/column indexes. That makes further work with it easier. Looping over all board positions is just for z in board, the four neighbors of a board position z are just z + 1j**k (for k in 0 to 3), and I don’t need to check borders because board.get just returns “None” if I request an invalid position.

After this preparation, I just take the tree and recursively dive with it into each board position. Similar to how you’d search a single word, but with the tree instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def findWords(self, board, words):

root = {}
for word in words:
node = root
for c in word:
node = node.setdefault(c, {})
node[None] = True
board = {i + 1j*j: c
for i, row in enumerate(board)
for j, c in enumerate(row)}

found = []
def search(node, z, word):
if node.pop(None, None):
found.append(word)
c = board.get(z)
if c in node:
board[z] = None
for k in range(4):
search(node[c], z + 1j**k, word + c)
board[z] = c
for z in board:
search(root, z, '')

return found

https://discuss.leetcode.com/topic/16782/python-code-use-trie-and-dfs-380ms

Python code use trie and dfs 380ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
# @param {character[][]} board
# @param {string[]} words
# @return {string[]}
def findWords(self, board, words):
#make trie
trie={}
for w in words:
t=trie
for c in w:
if c not in t:
t[c]={}
t=t[c]
t['#']='#'
self.res=set()
self.used=[[False]*len(board[0]) for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
self.find(board,i,j,trie,'')
return list(self.res)

def find(self,board,i,j,trie,pre):
if '#' in trie:
self.res.add(pre)
if i<0 or i>=len(board) or j<0 or j>=len(board[0]):
return
if not self.used[i][j] and board[i][j] in trie:
self.used[i][j]=True
self.find(board,i+1,j,trie[board[i][j]],pre+board[i][j])
self.find(board,i,j+1,trie[board[i][j]],pre+board[i][j])
self.find(board,i-1,j,trie[board[i][j]],pre+board[i][j])
self.find(board,i,j-1,trie[board[i][j]],pre+board[i][j])
self.used[i][j]=False

https://discuss.leetcode.com/topic/22858/python-dfs-solution-directly-use-trie-implemented

Python dfs solution (directly use Trie implemented).

Here is an implementation based on Implement Trie in LeetCode. TrieNode, Trie, Solution are treated as seperated classes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class TrieNode():
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False

class Trie():
def __init__(self):
self.root = TrieNode()

def insert(self, word):
node = self.root
for w in word:
node = node.children[w]
node.isWord = True

def search(self, word):
node = self.root
for w in word:
node = node.children.get(w)
if not node:
return False
return node.isWord

class Solution(object):
def findWords(self, board, words):
res = []
trie = Trie()
node = trie.root
for w in words:
trie.insert(w)
for i in xrange(len(board)):
for j in xrange(len(board[0])):
self.dfs(board, node, i, j, "", res)
return res

def dfs(self, board, node, i, j, path, res):
if node.isWord:
res.append(path)
node.isWord = False
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
return
tmp = board[i][j]
node = node.children.get(tmp)
if not node:
return
board[i][j] = "#"
self.dfs(board, node, i+1, j, path+tmp, res)
self.dfs(board, node, i-1, j, path+tmp, res)
self.dfs(board, node, i, j-1, path+tmp, res)
self.dfs(board, node, i, j+1, path+tmp, res)
board[i][j] = tmp

19ms, 90.34%, September 23, 2016

https://discuss.leetcode.com/topic/9826/my-19ms-accepted-c-code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
m = board.size();
n = board[0].size();
for(int x=0; x<m; x++)
for(int y=0; y<n; y++)
if(isFound(board, word.c_str(), x, y))
return true;
return false;
}

private:
int m;
int n;
bool isFound(vector<vector<char>>& board, const char* w, int x, int y){
if(x<0||y<0||x>=m||y>=n||board[x][y]=='\0'||*w!=board[x][y])
return false;
if(*(w+1)=='\0') return true;
char t = board[x][y];
board[x][y] = '\0';
if(isFound(board, w+1, x-1, y)||isFound(board, w+1, x+1, y)||isFound(board, w+1, x, y-1)||isFound(board, w+1, x, y+1))
return true;
board[x][y] = t;
return false;
}
};

47ms, September 23, 2016

https://discuss.leetcode.com/topic/7907/accepted-very-short-java-solution-no-additional-space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public boolean exist(char[][] board, String word) {
char[] w= word.toCharArray();
for(int y=0; y<board.length; y++)
for(int x=0; x<board[y].length; x++)
if(exist(board, y, x, w, 0)) return true;
return false;
}

private boolean exist(char[][] board, int y, int x, char[] word, int i){
if(i==word.length) return true;
if(y<0||x<0||y==board.length||x==board[y].length) return false;
if(board[y][x] != word[i]) return false;
board[y][x] ^= 256;
boolean exist = exist(board, y, x+1, word, i+1)
|| exist(board, y, x-1, word, i+1)
|| exist(board, y+1, x, word, i+1)
|| exist(board, y-1, x, word, i+1);
board[y][x] ^= 256;
return exist;
}
}
谢谢你,可爱的朋友。