Open ShannonChenCHN opened 3 years ago
ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago 一个文本文件，大约有一万行，每行一个词，要求找出该文件中是否存在某个指定的单词，请给出主要思想和时间复杂度分析。
定义数节点结构：首先定义一个表征 Trie 节点的数据结构，其实就是一个树的节点，每个节点包括 0~26 个子节点。 另外，每个节点有一个变量来记录是否是叶节点。
插入单词：从前往后依次遍历单词的每一个字符，每位字符对应树的每一层（根节点为空，所以根节点除外）， 如果树中对应的层中没有该字符，就在这一层中该字符对应的位置（0~25）插入一个节点
打印所有单词：这里可以用先序遍历来实现，核心思路在于记录路径。
我们可以用一个数组来保存所有的“浏览”过的路径，如果遇到一个是单词结尾字符的节点，就打印数组中的所有字符。
查找单词：满足两个条件，一是单词的每个字母都有对应的节点，二是单词末尾字符对应的节点正好是单词结尾节点
完整示例代码见这里。
#include <iostream>
/// Alphabet size (# of symbols)
#define ALPHABET_SIZE 26
/// Calucate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
/// Converts key current character into index
/// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
/// Trie node
struct TrieNode {
TrieNode *children[ALPHABET_SIZE];
bool isLeaf;
};
/// Returns new trie node (initialized to NULLs)
TrieNode *creatNode(void) {
TrieNode *pNode = new TrieNode;
pNode->isLeaf = false;
for (int i = 0; i < ALPHABET_SIZE; i++) {
pNode->children[i] = nullptr;
}
return pNode;
}
/// If not present, inserts key into trie
/// If the key is prefix of trie node, just
/// marks leaf node
void insert(TrieNode *pRoot, const char *key) {
// 1. get the length of the key
int keyLength = (int)strlen(key);
// 2. iterate the key string, if the character
// is not presented in the corresponding level,
// insert a new node.
TrieNode *pNode = pRoot;
for (int level = 0; level < keyLength; level++) {
int indexOfCurrentChar = CHAR_TO_INDEX(key[level]);
if (pNode->children[indexOfCurrentChar] == nullptr) {
pNode->children[indexOfCurrentChar] = creatNode();
} else {
pNode->children[indexOfCurrentChar]->isLeaf = false;
}
pNode = pNode->children[indexOfCurrentChar];
}
// 3. Set the node that doesn't have any children as leaf.
pNode->isLeaf = true;
for (int index = 0; index < ALPHABET_SIZE; index++) {
if (pNode->children[index] != nullptr) {
pNode->isLeaf = false;
}
}
}
void printTrie(TrieNode *pRoot) {
// pre-order
for (int index = 0; index < ALPHABET_SIZE; index++) {
TrieNode *currentNode = pRoot->children[index];
if (currentNode != nullptr) {
char rootChar = index + 'a';
printf("%c", rootChar);
if (currentNode->isLeaf) {
printf(", ");
} else {
printTrie(currentNode);
}
}
}
}
int main(int argc, const char * argv[]) {
// Input keys (use only 'a' through 'z' and lower case)
// The array used to hold input keys is two-dimensional array
char keys[][8] = {"the", "a", "there", "answer",
"any", "by", "bye", "their"};
TrieNode *pRoot = creatNode();
// Construct Trie
for (int i = 0; i < ARRAY_SIZE(keys); i++) {
insert(pRoot, keys[i]);
}
printTrie(pRoot);
return 0;
}2021.03.27 09:00 pm ~ 2021.03.27 10:10 pm
参考：
主要有四个环节：
需要注意的是 Trie 和多叉树的区别，建议画图结合图来看。
class Trie {
class TrieNode {
var isEnd: Bool = false
var links: [Character: TrieNode] = [:]
}
var root: TrieNode = TrieNode()
/** Initialize your data structure here. */
init() {
}
/** Inserts a word into the trie. */
func insert(_ word: String) {
var node: TrieNode = root
for char in word {
if node.links[char] == nil {
node.links[char] = TrieNode()
}
node = node.links[char]!
}
node.isEnd = true
}
/** Returns if the word is in the trie. */
func search(_ word: String) -> Bool {
var node: TrieNode = root
for char in word {
if node.links[char] == nil {
return false
}
node = node.links[char]!
}
return node.isEnd
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func startsWith(_ prefix: String) -> Bool {
var node: TrieNode = root
for char in prefix {
if node.links[char] == nil {
return false
}
node = node.links[char]!
}
return true
}
}
2021.03.27 10:10 pm ~ 10:50 pm
class WordDictionary {
class TrieNode {
var isEnd: Bool = false
var links: [Character: TrieNode] = [:]
}
var root: TrieNode = TrieNode()
/** Initialize your data structure here. */
init() {
}
/** Inserts a word into the trie. */
func addWord(_ word: String) {
var node: TrieNode = root
for char in word {
if node.links[char] == nil {
node.links[char] = TrieNode()
}
node = node.links[char]!
}
node.isEnd = true
}
/** Returns if the word is in the trie. */
func search(_ word: String) -> Bool {
return match(Array(word), 0, root)
}
func match(_ characters: [Character], _ start: Int, _ trieNode: TrieNode) -> Bool {
// 最后一位字符
guard start < characters.count else {
return trieNode.isEnd
}
// 普通字符
let char = characters[start]
if char != "." {
return trieNode.links[char] != nil && match(characters, start+1, trieNode.links[char]!)
}
// 通配符
var node: TrieNode = trieNode
for (char, nextNode) in node.links {
if match(characters, start+1, nextNode) {
return true
}
}
return false
}
}
题目列表
总结：