leetcode - Word Search II

leetcode - Word Search II

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

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 (index
child[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;
			}
			
		}
	}
};