Trie - leetcode [字典树/前缀树]

208. Implement Trie (Prefix Tree)

字母的字典树每个节点要定义一个大小为26的子节点指针数组,然后用一个标志符用来记录到当前位置为止是否为一个词,初始化的时候讲26个子节点都赋为空。那么insert操作只需要对于要插入的字符串的每一个字符算出其的位置,然后找是否存在这个子节点,若不存在则新建一个,然后再查找下一个。查找词和找前缀操作跟insert操作都很类似,不同点在于若不存在子节点,则返回false。查找次最后还要看标识位,而找前缀直接返回true即可。

class TrieNode {
public:
  TrieNode *child[26];
  bool isWord;
  TrieNode() : isWord(false){
    for (auto &a : child)   a = NULL;
  }
};

211. Add and Search Word - Data structure design

唯一不同的地方就是search的函数需要重新写一下,因为这道题里面'.'可以代替任意字符,所以一旦有了'.',就需要查找所有的子树,只要有一个返回true,整个search函数就返回true,典型的DFS的问题

212.Word Search II

在这题中只要实现字典树中的insert功能就行了,查找单词和前缀就没有必要了,然后DFS的思路跟之前那道Word Search 词语搜索基本相同

void search(vector<vector<char> > &board, TrieNode *p, int i, int j, vector<vector<bool> > &visit, vector<string> &res) {
if (!p->str.empty()) {
res.push_back(p->str);
p->str.clear();
}
int d[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
visit[i][j] = true;
for (auto &a : d) {
int nx = a[0] + i, ny = a[1] + j;
if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && !visit[nx][ny] && p->child[board[nx][ny] - 'a']) {
search(board, p->child[board[nx][ny] - 'a'], nx, ny, visit, res);
}
}
visit[i][j] = false;
}
上一篇:BestCoder Round #85 hdu5776 sum


下一篇:Java基础知识强化之IO流笔记03:throws的方式处理异常