Algorithm

LintCode/Word Search II

Problem Summary

Given a matrix of lower alphabets and a dictionary, find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position.

Solution

First, we use Trie to record the words in the dictionary.

Second, we iterate the indices of the starting position of strings. For each (i,j), if there are words beginning with matrix[i][j], we use BFS to search for all possible words starting here. During the search, we can greatly cut the search tree with the help of the Trie we built.

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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
class Solution {
public:
	const int dir[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
	struct Node
	{
		char c;
		bool is_word;
		int idx;
		Node *p[26];
		Node() { idx = 0; is_word = false; memset(p,0,sizeof(p)); }
		Node(char c1)
		{
			c = c1;
			idx = 0;
			is_word = false;
			memset(p,0,sizeof(p));
		}
	};
	class Trie
	{
	public:
		Node *root;
		Trie() { root = new Node; }
		void insert(string &w,int idx)
		{
			Node *cur = root;
			for (int i = 0; i < w.length(); ++i)
			{
				char c = w[i]-'a';
				if (!cur->p[c])
					cur->p[c] = new Node(c);
				cur = cur->p[c];
			}
			cur->is_word = true;
			cur->idx = idx;
		}
	};
	struct Status
	{
		int x,y;
		Node *ptr;
		vector<bool> used;
		Status(int x1,int y1,Node *p1,vector<bool> &u)
		{
			x = x1; y = y1; ptr = p1; used = u;
		}
	};
	void bfs(int x,int y,Node *p1,int n,int m,vector<vector<char> > &board,unordered_set<string> &res, vector<string> &words)
	{
		queue<Status> q;
		vector<bool> u(n*m,0);
		u[x*m+y] = true;
		Status init(x,y,p1,u);
		q.push(init);
		while (!q.empty())
		{
			Status cur = q.front();
			q.pop();
			if (cur.ptr->is_word)
				res.insert(words[cur.ptr->idx]);
			for (int i = 0; i < 4; ++i)
			{
				int tx = cur.x + dir[i][0];
				if (tx < 0 || tx >= n)
					continue;
				int ty = cur.y + dir[i][1];
				if (ty < 0 || ty >= m || cur.used[tx*m+ty])
					continue;
				if (!cur.ptr->p[board[tx][ty]-'a'])
					continue;
				Status next(tx,ty,cur.ptr->p[board[tx][ty]-'a'],cur.used);
				next.used[tx*m+ty] = true;
				q.push(next);
			}
		}
	}
	/*
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    vector<string> wordSearchII(vector<vector<char> > &board, vector<string> &words) {
    	int n = board.size();
    	if (n==0)
    		return vector<string>();
    	unordered_set<string> res;
    	Trie trie;
    	for (int i = 0; i < words.size(); ++i)
    		trie.insert(words[i],i);
    
    	int m = board[0].size();
    	for (int i = 0; i < n; ++i)
    		for (int j = 0; j < m; ++j)
    			if (trie.root->p[board[i][j]-'a'])
    				bfs(i,j,trie.root->p[board[i][j]-'a'],n,m,board,res,words);
    	return vector<string>(res.begin(),res.end());
    }
};