频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
leetcode - Word Search II
2015-05-20 10:43:04         来源:bupt8846的专栏  
收藏   我要投稿

 

 

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

 

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


 

分析:

1、使用字典树。

2、用一个指针指向字典树的某个结点,代表字符串的某一位。这样在递归过程中,判断一个字符串在字典树中是否是前缀时,不用从字符串的开头开始遍历字典树。

3、标记某个位置是否被访问,用二维数组而不是哈希表。

 

 

class TrieNode {
public:
	// Initialize your data structure here.
	TrieNode() {
		isend = false;
		for (int i = 0; i<26; ++i)
		{
			child[i] = nullptr;
		}
	}
	bool isend;
	TrieNode* child[26];
};

class Trie {
public:
	Trie() {
		root = new TrieNode();
	}

	// Inserts a word into the trie.
	void insert(string s) {
		if (s.empty())
			return;
		int index = 0;
		TrieNode* cur = root;
		while (indexchild[temp] == nullptr)
				break;
			else
			{
				cur = cur->child[temp];
				++index;
			}
		}
		if (index == s.size())
		{
			cur->isend = true;
			return;
		}

		while (indexchild[temp] = new TrieNode();
			cur = cur->child[temp];
			++index;
		}
		cur->isend = true;
	}

    //返回的第二个参数是指向最后一个字母的指针
	pair startsWith(string prefix) {
		if (prefix.empty())
			return make_pair(true, nullptr);
		int index = 0, temp = 0;
		TrieNode* cur = root;
		while (indexchild[temp] == nullptr)
				return make_pair(false, nullptr);
			else
			{
				++index;
				cur = cur->child[temp];
			}
		}
		return make_pair(true, cur);
	}


	TrieNode* root;
};


class Solution {
public:

	Trie m_tree;

	vector findWords(vector>& board, vector& words) {
		vector res;
		if (words.empty() || board.empty() || board[0].empty())
			return res;
		int rows = board.size(), cols = board[0].size();
		size_t sum = rows*cols;
		for (auto &word : words)
		{
			if (word.size() <= sum)
			{
				m_tree.insert(word);
			}
				
		}
        
        //注意,应该用二维数组标识某个位置是否已经被访问,用set的话花费时间过大
        vector> visit(rows,vector(cols,false));
        //为了返回值没有重复,应该使用unordered_set
		unordered_set result;
		for (int i = 0; iisend)
					{
						result.insert(str);
					}
				    visit[i][j]=true;
					findWords_core(board, i, j, p.second, result, visit, str);
					visit[i][j]=false;
				}
			}
		}
		for (auto &w : result)
			res.push_back(w);
		return res;
	}


	void findWords_core(vector>& board, int i, int j, TrieNode* root, unordered_set &res,  vector> &visit, string str)
	{
		int rows = board.size(), cols = board[0].size();
		if (i + 1child[c - 'a'])
			{
				visit[i+1][j]=true;
				string tmp = str + string(1, c);
				if (root->child[c - 'a']->isend)
				{
					res.insert(tmp);
				}
				findWords_core(board, i + 1, j, root->child[c - 'a'], res, visit, tmp);
					visit[i+1][j]=false;
			}
			
		}
		if (i - 1 >= 0 && visit[i-1][j] == false)
		{
			char c = board[i - 1][j];
			
			if (root->child[c - 'a'])
			{
			    visit[i-1][j] =true;
				string tmp = str + string(1, c);
				if (root->child[c - 'a']->isend)
				{
					res.insert(tmp);
				}
				findWords_core(board, i - 1, j, root->child[c - 'a'], res, visit, tmp);
				visit[i-1][j] =false;
			}
			
		}
		if (j + 1child[c - 'a'])
			{
				string tmp = str + string(1, c);
				visit[i][j+1]=true;
				if (root->child[c - 'a']->isend)
				{
					res.insert(tmp);
				}
				findWords_core(board, i, j + 1, root->child[c - 'a'], res, visit, tmp);
				visit[i][j+1]=false;
			}
			
		}
		if (j - 1 >= 0 && visit[i][j-1]==false)
		{
			char c = board[i][j - 1];
			if (root->child[c - 'a'])
			{
				string tmp = str + string(1, c);
			visit[i][j-1]=true;
				if (root->child[c - 'a']->isend)
				{
					res.insert(tmp);
				}
				findWords_core(board, i, j - 1, root->child[c - 'a'], res, visit, tmp);
				visit[i][j-1]=false;
			}
			
		}
	}
};


 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:leetcode 207: Course Schedule
下一篇:c++ 中的空指针和void指针
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站