[leetcode] 212. Word Search II

[leetcode] 212. Word Search II

Description

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.

Example:

Input:

board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v']]words = ["oath","pea","eat","rain"]

Output:

["eat","oath"]

Note:

All inputs are consist of lowercase letters a-z.The values of words are distinct.

分析

题目的意思是：给定一个二维字符矩阵，和一个单词列表，问有多少个单词能够由二维字符矩阵的一条路径构成，其中相同字符单元只能用一次。

首先建立了一个trie的树，然后在这个字典树里面查找。

代码

class TrieNode{public: int isWord; vector next; TrieNode(){ isWord=-1; next=vector(26,NULL); }};class Solution {private: TrieNode* root;public: vector findWords(vector>& board, vector& words) { root=new TrieNode(); buildTree(words,root); set res; for(int i=0;i(res.begin(),res.end()); } void findWords(set& res, vector>& board, vector& words, TrieNode* node, int r, int c){ if(board[r][c] == '.' || !node->next[board[r][c]-'a']) return; TrieNode* after=node->next[board[r][c]-'a']; if(after->isWord>-1){ res.insert(words[after->isWord]); } char letter=board[r][c]; board[r][c]='.'; if(r-1>=0){ findWords(res,board,words,after,r-1,c); } if(r+1=0){ findWords(res,board,words,after,r,c-1); } if(c+1& words,TrieNode* root){ TrieNode* cur; for(int i=0;inext[c-'a']){ cur->next[c-'a']=new TrieNode(); } cur=cur->next[c-'a']; } cur->isWord=i; } }};

参考文献

​​212. Word Search II​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。