原题链接：
https://www.lintcode.com/zh-cn/problem/word-search-ii/
题目描述
给出一个由小写字母组成的矩阵和一个字典。找出所有同时在字典和矩阵中出现的单词。一个单词可以从矩阵中的任意位置开始，可以向左/右/上/下四个相邻方向移动。
样例
给出矩阵：
doaf
agai
dcan
和字典： {"dog", "dad", "dgdg", "can", "again"}
返回 {"dog", "dad", "can", "again"}
dog: doaf agai dcan dad:
doaf agai dcan can:
doaf agai dcan again:
doaf agai dcan
挑战
使用单词查找树来实现你的算法
题目解析
题目的给出了一个由小写字母组成的矩阵（实际上是一个二维数组，当然想象成矩阵确实更容易理解）。我们可以从矩阵的任意一个字母开始，上下左右移动。移动经过的字母可以自称一个个的单词。在这些能够组成的单词中，有哪些单词是跟题目中给出的字典（实际上是一个数组，数组里面有几个单词）中的单词是一致的。或者说，题目给出的字典中的单词，是否能够能从矩阵中组成。
题目还有一个进阶的要求，就是算法采用单词查找树来完成。当然，这不是必须的要求。
思路
思路一
这题目并不简单。首先的想法是想出办法，给出一个单词，判断该单词是不是能由矩阵组成。将所有的字典中的单词都采用这种方式遍历一遍，那么就完成题目的要求了。现在问题是，如何判断该单词是不是能由矩阵组成呢。这个问题其实就是的问题。这里就不展开了，有兴趣的自己去看下。
思路二
采用字典树。暂时挖个坑，以后再写。
代码（Python）
思路一代码
class Solution: """ @param board: A list of lists of character @param words: A list of string @return: A list of string """ def wordSearchII(self, board, words): result = [] if not board or not words: return result #遍历字符串数组，判断字符串是否可以由矩阵数组组成，若是，则添加到数组里面 for word in words: isWordExistInBoard = self.wordExistInBoard(board,word) if isWordExistInBoard: result.append(word) return result """ 自定义的方法：判断字符串word是否可以由board矩阵里面的字母组成 @param board: A list of lists of character @param words: string @return: 字符串word是否可以由board矩阵里面的字母组成 """ def wordExistInBoard(self,board,word): #初始化访问数组boardValid，为True代表可访问，为False代表之前已经用过，不能再用 boardValid = [] for i in range(len(board)): boardValid.append([]) for j in range(len(board[0])): boardValid[i].append(True) #遍历board数组，查找出与word第一个字符相等的位置，开始进行判断 for i in range(len(board)): for j in range(len(board[0])): if board[i][j] == word[0]: exist = self.wordExist(board,word,i,j,1,boardValid) if exist: return True return False """ 自定义的方法：判断字符串word是否可以由board矩阵里面的字母组成 @param board: A list of lists of character @param words: string @param i: board的当前横坐标 @param j: board的当前纵坐标 @param currentLength: 当前准备要得到结果的currentLength长度 @param boardValid: 字符是否可以访问的数组 @return: 字符串word是否可以由board矩阵里面的字母组成 """ def wordExist(self,board,word,i,j,currentLength,boardValid): #长度足够 if currentLength == len(word) + 1: return True #超出范围 if i<0 or i>=len(board) or j<0 or j>=len(board[0]): return False #已经用过，不可用 if boardValid[i][j] == False: return False #字符不匹配 if board[i][j] != word[currentLength-1]: return False #设置标志位，当前字符串已访问过 boardValid[i][j] = False #判断上下左右 upExist = self.wordExist(board,word,i,j-1,currentLength+1,boardValid) downExist = self.wordExist(board,word,i,j+1,currentLength+1,boardValid) leftExist = self.wordExist(board,word,i-1,j,currentLength+1,boardValid) rightExist = self.wordExist(board,word,i+1,j,currentLength+1,boardValid) #能组成 if upExist or downExist or leftExist or rightExist: return True else: #失败，需要重置标志位 boardValid[i][j] = True return False复制代码
谦言忘语
个人目前只懂一丁点python语法，所以不做语法上的优化，而且整体代码风格效果会尽量跟C语言趋于一致。