给定一个 m x n 二维字符网格 board 和一个单词字符串列表 words 返回所有二维网格上的单词 。单词必须按照字母顺序通过 相邻的单元格 内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。示例 1输入board [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words [“oath”,“pea”,“eat”,“rain”]输出[“eat”,“oath”]示例 2输入board [[“a”,“b”],[“c”,“d”]], words [“abcb”]输出[]提示m board.lengthn board[i].length1 m, n 12board[i][j] 是一个小写英文字母1 words.length 3 * 104^{4}41 words[i].length 10words[i] 由小写英文字母组成words 中的所有字符串互不相同我们可以先把words中的所有单词存入字典树然后遍历board中的每个位置看从该位置出发的所有路径是否存在于字典树中classNode{public:vectorNode*nextvectorNode*(26,nullptr);boolisEndfalse;~Node(){for(Node*oneNode:next){deleteoneNode;}}};classSolution{public:Solution(){rootnewNode();}~Solution(){deleteroot;}vectorstringfindWords(vectorvectorcharboard,vectorstringwords){for(strings:words){Node*curNoderoot;for(charc:s){if(curNode-next[c-a]nullptr){curNode-next[c-a]newNode();}curNodecurNode-next[c-a];}curNode-isEndtrue;}intmboard.size();intnboard[0].size();vectorstringans;unordered_setintseen;string curAns;// 从每个可能的起点开始搜索for(inti0;im;i){for(intj0;jn;j){doFind(board,root,i,j,seen,curAns,ans);}}returnans;}private:Node*root;// 返回值是curNode是否已经没用了// 当curNode没有子节点即叶子结点且当前节点表示的单词已经加入到了答案中时该节点就没用了// 没用的节点父节点就可以删除即剪枝防止后续再次搜索该单词booldoFind(vectorvectorcharboard,Node*curNode,inti,intj,unordered_setintseen,stringcurAns,vectorstringans){// 如果超出board范围if(i0||iboard.size()||j0||jboard[0].size()){returnfalse;}// 如果已经将该格子的字母加入了当前答案单词中intkeyi*13j;if(seen.find(key)!seen.end()){returnfalse;}// 如果以该格子为结尾的前缀不属于任何单词charcboard[i][j];if(curNode-next[c-a]nullptr){returnfalse;}curNodecurNode-next[c-a];// 将当前节点代表的字母加入答案并记录已处理的格子seen.insert(key);curAnsc;// 已经是完整的一个单词if(curNode-isEnd){// 将单词加入答案ans.push_back(curAns);// 是否是完整单词标志位置为false防止同一单词重复加入答案curNode-isEndfalse;}// 接下来的四个下一步intdirs[4][2]{{-1,0},{1,0},{0,-1},{0,1}};// 遍历每个可能的下一步for(autod:dirs){intniid[0];intnjjd[1];if(ni0||niboard.size()||nj0||njboard[0].size()){continue;}boolremoveChilddoFind(board,curNode,ni,nj,seen,curAns,ans);// 如果当前下一步所代表的节点可以被删除了if(removeChild){charncboard[ni][nj];deletecurNode-next[nc-a];curNode-next[nc-a]nullptr;}}// 回溯curAns.pop_back();seen.erase(key);// 剪枝如果没有下一个节点且当前节点不是一个完整单词的最后一个字母则curNode可被删除if(!curNode-isEnd){for(Node*oneNode:curNode-next){if(oneNode!nullptr){returnfalse;}}}returntrue;}};m board.size()n board[0].size()L 为所有 words 中字符总数l 为 words 中最长单词长度。则构建Trie的时间复杂度为O(L)搜索的起点数量为O(nm)每次搜索时递归深度不会超过l每次递归有3个可能的下一步因为不能回到上一步因此每次搜索的时间复杂度为O(3l^{l}l)因此总时间复杂度为O(Lmn3l^{l}l)。空间复杂度方面字典树需要O(L)空间递归搜索时递归栈所需空间为O(l)因此总空间复杂度为O(L)。