郑州网站seo,怎样做自己介绍网站,wordpress 判断是否页面,网站没有备案可以访问吗1. 题目
给定一个二维网格 board 和一个字典中的单词列表 words#xff0c;找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的…1. 题目
给定一个二维网格 board 和一个字典中的单词列表 words找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words [oath,pea,eat,rain] and board
[[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]
]
输出: [eat,oath]
说明:
你可以假设所有输入都由小写字母 a-z 组成。类似题目LeetCode 79. 单词搜索回溯DFS
2. Trie树DFS
先将单词插入Trie树再遍历board中的每个字符以每个字符为起点DFS在Trie中查找
class TrieNode
{
public:string str;TrieNode *next[26];bool isEnd;TrieNode():isEnd(false) {memset(next, 0, sizeof(TrieNode*)*26);}
};
class Trie
{
public:TrieNode *root;Trie(){root new TrieNode();}~Trie(){destroy(root);}void destroy(TrieNode *root){if(root NULL)return;for(int i 0; i 26; i)destroy(root-next[i]);delete root;}void insert(string word){TrieNode *cur root;for(char s:word){if(cur-next[s-a] NULL)cur-next[s-a] new TrieNode();cur cur-next[s-a];}cur-isEnd true;cur-str word;//存储该单词}
};class Solution {Trie tree;
public:vectorstring findWords(vectorvectorchar board, vectorstring words) {for(auto word : words)tree.insert(word);int i, j;vectorstring ans;for(i 0; i board.size(); i)for(j 0; j board[0].size(); j)dfs(board,tree.root,i,j,ans);return ans;}void dfs(vectorvectorchar b, TrieNode *cur, int x, int y, vectorstring ans){if(cur-isEnd)//先检查字符是不是而不是坐标万一坐标出界但是当前字符串结尾{cur-isEnd false;//该单词取出放入答案关闭ans.push_back(cur-str);return;}if(x 0 || x b.size() || y 0 || y b[0].size()) return;if(b[x][y] # || !cur || (b[x][y] ! # cur-next[b[x][y]-a] NULL))return;char ch b[x][y];cur cur-next[ch-a];b[x][y] #; //标记走过dfs(b,cur,x1,y,ans);dfs(b,cur,x-1,y,ans);dfs(b,cur,x,y1,ans);dfs(b,cur,x,y-1,ans);b[x][y] ch; //恢复现场}
};
