[TOC]
- 结点本身不存完整单词
- 从根结点到某一结点路径上，所经过的字符连接起来，为该结点对应的字符串
- 每个结点的所有子结点路径，所代表的字符都不相同
class Trie {
struct TrieNode {
map<char, TrieNode*>child_table;
int end;
TrieNode(): end(0) {}
};
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *curr = root;
for (int i = 0; i < word.size(); i++) {
if (curr->child_table.count(word[i]) == 0)
curr->child_table[word[i]] = new TrieNode();
curr = curr->child_table[word[i]];
}
curr->end = 1;
}
/** Returns if the word is in the trie. */
bool search(string word) {
return find(word, 1);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return find(prefix, 0);
}
private:
TrieNode* root;
bool find(string s, int exact_match) {
TrieNode *curr = root;
for (int i = 0; i < s.size(); i++) {
if (curr->child_table.count(s[i]) == 0)
return false;
else
curr = curr->child_table[s[i]];
}
if (exact_match)
return (curr->end) ? true : false;
else
return true;
}
};
- 连通问题
- 组队问题
class UnionFind {
public:
UnionFind(vector<vector<char>>& grid) {
count = 0;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent.push_back(i * n + j);
++count;
}
else {
parent.push_back(-1);
}
rank.push_back(0);
}
}
}
//递归
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unite(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] < rank[rooty]) {
swap(rootx, rooty);
}
parent[rooty] = rootx;
if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
--count;
}
}
int getCount() const {
return count;
}
private:
vector<int> parent;
vector<int> rank;
int count;
};