本文主要是介绍LeetCode 题解（92）: 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.
题解：
用Word Search I 依次查找words里的每个单词会超时。思路由每次用Word Search I查找word 是否在board里转为, 直接看board上的每个字符，如果该字符存在于由words构建的Trie中，则进行DFS，直到递归到找到某个单词，将该单词加入到result中，同时从Trie中删除该单词。注意Trie需要四个方法：insert, search, searchPre, remove。
C++版：
struct TrieNode {bool leaf;TrieNode* children[26];TrieNode() {leaf = false;for(int i = 0; i < 26; i++) {children[i] = NULL;}}
};class Trie {
public:TrieNode* root;Trie() {root = new TrieNode();}~Trie() {delete root;}void insert(string s) {TrieNode* p = root;for(int i = 0; i < s.length(); i++) {if(p->children[s[i]-'a'] == NULL) {TrieNode* newNode = new TrieNode();p->children[s[i]-'a'] = newNode;}if(i == s.length() - 1)p->children[s[i]-'a']->leaf = true;p = p->children[s[i]-'a'];}}bool search(string s) {if(s.length() == 0)return false;int i = 0;TrieNode* p = root;while(i < s.length()) {if(p->children[s[i]-'a'] == NULL)return false;else {p = p->children[s[i]-'a'];i++;}}if(p->leaf == false)return false;return true;}bool searchPre(string s) {if(s.length() == 0)return false;int i = 0;TrieNode* p = root;while(i < s.length()) {if(p->children[s[i]-'a'] == NULL)return false;else {p = p->children[s[i]-'a'];i++;}}return true;}void remove(string s) {if(s.length() == 0)return;if(search(s) == false)return;int i = 0;TrieNode* p = root;while(i < s.length()) {p = p->children[s[i]-'a'];i++;}p->leaf = false;}
};class Solution {
public:vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {vector<string> results;if(words.size() == 0)return results;Trie tree;for(int i = 0; i < words.size(); i++) {tree.insert(words[i]);}vector<vector<bool>> used(board.size(), vector<bool>(board[0].size(), false));for(int i = 0; i < board.size(); i++) {for(int j = 0; j < board[0].size(); j++) {string s;s.push_back(board[i][j]);if(tree.search(s)) {results.push_back(s);tree.remove(s);}else if(tree.searchPre(s)){used[i][j] = true;exist(board, tree, i+1, j, used, s, results);exist(board, tree, i-1, j, used, s, results);exist(board, tree, i, j+1, used, s, results);exist(board, tree, i, j-1, used, s, results);used[i][j] = false;}s.pop_back();}}return results;}void exist(vector<vector<char>>& board, Trie &tree, int i, int j, vector<vector<bool>> & used, string &s, vector<string>& results) {if(i >= board.size() || i < 0 || j >= board[0].size() || j < 0)return;if(used[i][j] == true)return;s.push_back(board[i][j]);if(tree.search(s)) {results.push_back(s);tree.remove(s);}if(tree.searchPre(s)) {used[i][j] = true;exist(board, tree, i+1, j, used, s, results);exist(board, tree, i-1, j, used, s, results);exist(board, tree, i, j+1, used, s, results);exist(board, tree, i, j-1, used, s, results);used[i][j] = false;}s.pop_back();}
};Java 版：
class TrieNode {boolean leaf;TrieNode[] children;TrieNode() {leaf = false;children = new TrieNode[26];}
}class Trie {TrieNode root = new TrieNode();void insert(String s) {if(s.length() == 0)return;TrieNode p = root;int i = 0;while(i < s.length()) {if(p.children[s.charAt(i)-'a'] == null) {TrieNode newNode = new TrieNode();p.children[s.charAt(i)-'a'] = newNode;}p = p.children[s.charAt(i)-'a'];i += 1;}p.leaf = true;}void remove(String s) {if(s.length() == 0)return;if(search(s) == false)return;TrieNode p = root;int i = 0;while(i < s.length()) {p = p.children[s.charAt(i)-'a'];i += 1;}p.leaf = false;}boolean search(String s) {if(s.length() == 0)return false;TrieNode p = root;int i = 0;while(i < s.length()) {if(p.children[s.charAt(i)-'a'] == null)return false;else {p = p.children[s.charAt(i)-'a'];i += 1;}}if(p.leaf == false)return false;return true;}boolean searchPre(String s) {if(s.length() == 0)return false;TrieNode p = root;int i = 0;while(i < s.length()) {if(p.children[s.charAt(i)-'a'] == null)return false;else {p = p.children[s.charAt(i)-'a'];i += 1;}}return true;}
}public class Solution {public List<String> findWords(char[][] board, String[] words) {List<String> result = new ArrayList<>();if(board.length == 0 || words.length == 0)return result;boolean[][] used = new boolean[board.length][board[0].length];Trie tree = new Trie();for(String word : words) {tree.insert(word);}for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {String s = Character.toString(board[i][j]);if(tree.search(s) == true) {result.add(s);tree.remove(s);}if(tree.searchPre(s) == true) {used[i][j] = true;exist(board, words, used, tree, result, s, i+1, j);exist(board, words, used, tree, result, s, i-1, j);exist(board, words, used, tree, result, s, i, j+1);exist(board, words, used, tree, result, s, i, j-1);used[i][j] = false;}}}return result;}void exist(char[][] board, String[] words, boolean[][] used, Trie tree, List<String> result, String s, int i, int j) {if(i < 0 || i >= board.length || j < 0 || j >= board[0].length)return;if(used[i][j] == true)return;s += Character.toString(board[i][j]);if(tree.search(s) == true) {result.add(s);tree.remove(s);}if(tree.searchPre(s) == true) {used[i][j] = true;exist(board, words, used, tree, result, s, i+1, j);exist(board, words, used, tree, result, s, i-1, j);exist(board, words, used, tree, result, s, i, j+1);exist(board, words, used, tree, result, s, i, j-1);used[i][j] = false;}s = s.substring(0, s.length()-1);}
}Python版：
Python版超时，但在local machine上test超时case结果是正确的。同时在Trie上加上记录单词个数的size变量，进一步优化，在local machine上 只需2~3ms。但还是超时。
class TrieNode:def __init__(self):self.leaf = Falseself.children = [None] * 26class Trie:def __init__(self):self.root = TrieNode()self.size = 0def insert(self, s):if len(s) == 0:returnp = self.rooti = 0while i < len(s):if p.children[ord(s[i])-ord('a')] is None:new_node = TrieNode()p.children[ord(s[i])-ord('a')] = new_nodep = p.children[ord(s[i])-ord('a')]i += 1p.leaf = Trueself.size += 1def remove(self, s):if len(s) == 0:returnif not self.search(s):returnp = self.rooti = 0while i < len(s):p = p.children[ord(s[i])-ord('a')]i += 1p.leaf = Falseself.size -= 1def search(self, s):if len(s) == 0:return Falsep = self.rooti = 0while i < len(s):if p.children[ord(s[i])-ord('a')] is None:return Falseelse:p = p.children[ord(s[i])-ord('a')]i += 1if not p.leaf:return Falsereturn Truedef searchPre(self, s):if len(s) == 0:return Falsep = self.rooti = 0while i < len(s):if p.children[ord(s[i])-ord('a')] is None:return Falseelse:p = p.children[ord(s[i])-ord('a')]i += 1return Trueclass Solution:# @param {character[][]} board# @param {string[]} words# @return {string[]}def findWords(self, board, words):result = []if len(board) == 0 or len(words) == 0:return resultused = [[False] * len(board[0]) for i in range(len(board)) ]tree = Trie()for word in words:tree.insert(word)for i in range(len(board)):for j in range(len(board[0])):if tree.size == 0:return results = board[i][j]if tree.search(s):result.append(s)tree.remove(s)if tree.searchPre(s):used[i][j] = Trueself.exist(board, words, used, tree, result, s, i+1, j)self.exist(board, words, used, tree, result, s, i-1, j)self.exist(board, words, used, tree, result, s, i, j+1)self.exist(board, words, used, tree, result, s, i, j-1)used[i][j] = Falsereturn resultdef exist(self, board, words, used, tree, result, s, i, j):if tree.size == 0:returnif i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):returnif used[i][j]:returns += board[i][j]if tree.search(s):result.append(s)tree.remove(s)if tree.searchPre(s):used[i][j] = Trueself.exist(board, words, used, tree, result, s, i+1, j)self.exist(board, words, used, tree, result, s, i-1, j)self.exist(board, words, used, tree, result, s, i, j+1)self.exist(board, words, used, tree, result, s, i, j-1)used[i][j] = Falses = s[0:len(s)-1]
这篇关于LeetCode 题解（92）: Word Search II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
