LeetCode Word Search II

最新推荐文章于 2019-05-10 03:49:42 发布

FightForProgrammer

最新推荐文章于 2019-05-10 03:49:42 发布

阅读量1.2k

点赞数

本文链接：https://blog.csdn.net/FightForProgrammer/article/details/46122711

版权

LeetCode 同时被 2 个专栏收录

44 篇文章

订阅专栏

LeetCode 算法实战

7 篇文章

订阅专栏

本文介绍了一种使用前缀树解决LeetCode上的单词搜索II问题的方法。通过构建前缀树来高效地在二维字符矩阵中查找给定单词列表中的所有单词。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

LeetCode 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.

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"] .

题目的意思是给定二维字符表和一些单词，然后返回能在字符表中找到的单词的集合。

解法：由于可能有很多的单词需要查找，单词一多，就有很多共有的前缀（如“abcd”和“abcf”的前缀是“abc”），这样一来就没有必要每个单词从头找起，于是想到了前缀树的解决方法：即把单词构建成前缀树，然后在字符表搜索，遇到满足题意的就加入结果集。

class Trie {
public:
	Trie* branch[26];
	bool isWord;//从根节点到当前节点组成的字符串是否是列表中的一个单词
	int index;//如果是列表中的一个单词，记录该单词在列表中的下标
public:
	Trie()
	{
		memset(branch, 0, sizeof(branch));
		isWord = false;
		index = 0;
	}
};

Trie* buildTrie(vector<string>& words)
{
	Trie* root = new Trie();
	for (int i = 0; i < words.size(); i++)
	{	
		Trie* p = root;
		for (int j = 0; j < words[i].size(); j++)
		{
			if (p->branch[words[i][j] - 'a'] == NULL)
			{
				p->branch[words[i][j] - 'a'] = new Trie();
			}
			p = p->branch[words[i][j] - 'a'];
		}

		p->isWord = true;
		p->index = i;//记录在words中的下标
	}

	return root;
}

void dfs(vector<vector<char> >& board, int i, int j, int row, int col, Trie* root, vector<string>& res, vector<string>& words)
{	
	if (board[i][j] == 'X')
		return;
	if (root->branch[board[i][j] - 'a'] == NULL)
		return;
	else
	{
		char t = board[i][j];
		if (root->branch[t - 'a']->isWord == true)
		{
			res.push_back(words[root->branch[t - 'a']->index]);//把words中位于index的单词加入结果集
			root->branch[t - 'a']->isWord = false;//标记次单词已访问过
		}

		board[i][j] = 'X';//标记已经搜索过
		//上下左右进行递归搜索
		if (i > 0)			dfs(board, i - 1, j, row, col, root->branch[t - 'a'], res, words);		
		if ((i + 1)<row)	dfs(board, i + 1, j, row, col, root->branch[t - 'a'], res, words);
		if (j > 0)			dfs(board, i, j - 1, row, col, root->branch[t - 'a'], res, words);
		if ((j + 1)<col)	dfs(board, i, j + 1, row, col, root->branch[t - 'a'], res, words);
		
		board[i][j] = t; //回溯
	}
}

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

	int wordLen = words.size(); 
	if (wordLen == 0)	return res;

	Trie *root = buildTrie(words);//把单词列表构建成前缀树

	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
		{
			//以每个字符作为起始点开始搜
			dfs(board, i, j, row, col, root, res, words);
		}
	}

	return res;
}