【Leetcode&C语言&Tire】208.Implement Trie (Prefix Tree) & 211.Design Add and Search Words Data Structure

这两道题难度是递进的关系，所以适合一起说。以下为题目入口

208.Implement Trie (Prefix Tree) 

211. Design Add and Search Words Data Structure

 

 

目录

208.Implement Trie (Prefix Tree)

实现

 211.Design Add and Search Words Data Structure

实现

---

 

208.Implement Trie (Prefix Tree)

实现

熟悉Tire树的话，这道题不难。但是我用C语言写增加操作时遇到了问题，每次增加前需要查找是否已经有该字符，没有就需要添加该字符。如果节点的结构体Node包括char str、Node **next[26]和bool is_word类型，那么势必在检查时需要遍历父节点next的所有节点。那么这样就将会是两个for循环，O(n²)级别的时间复杂度，你将达成Runtime Error。

拜读了这位大佬的代码后，看到了我没发现的细节。将字母的ASCII码和next的26个索引联系起来，每个字母都有‘a’的偏移量，字母a自然存在0索引位置，字母b也自然存在1索引位置，以此类推。这样做的好处在于可以以O(1)的时间复杂度找到是否存在该字符，甚至Node中可以不存储char str属性，我不用知道你代表什么字母，因为你的索引已经告诉我了。代码如下：

#define LEN 26
typedef struct Trie Trie;
struct Trie{
    bool is_word;
    Trie** next;
};

/** Initialize your data structure here. */

Trie* trieCreate() {
    Trie *trie = (Trie*)malloc(sizeof(Trie));
    trie->is_word=false;
    int space = sizeof(Trie*)*LEN;
    trie->next = (Trie **)malloc(space);
    memset(trie->next,0,space);
    return trie;
}

/** Inserts a word into the trie. */
void trieInsert(Trie* obj, char * word) {
  for(int i=0;word[i]!='\0';i++){
      if(!(obj->next[word[i]-'a']))
          obj->next[word[i]-'a'] = trieCreate();   
      obj=obj->next[word[i]-'a'];
  }
  obj->is_word = true;

}

bool recursiveSearch(Trie *obj, char *word, int index){
    if(word[index]=='\0')
    {
        return obj->is_word;
    }
    else{
        if(obj->next[word[index]-'a'])
            return recursiveSearch(obj->next[word[index]-'a'],word,index+1);
        else 
            return false;
    }
    
}

/** Returns if the word is in the trie. */
bool trieSearch(Trie *obj, char *word) {
    return recursiveSearch(obj,word,0);
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie* obj, char * prefix) {
  for(int i=0;prefix[i]!='\0';i++){
      if(!(obj->next[prefix[i]-'a']))
          return false;
      obj=obj->next[prefix[i]-'a']; 
  }
    return true;
}

void trieFree(Trie* obj) {
    free(obj->next);
    free(obj);
}

/**
 * Your Trie struct will be instantiated and called as such:
 * Trie* obj = trieCreate();
 * trieInsert(obj, word);
 
 * bool param_2 = trieSearch(obj, word);
 
 * bool param_3 = trieStartsWith(obj, prefix);
 
 * trieFree(obj);
*/

 211.Design Add and Search Words Data Structure

实现

这个问题在上个问题的基础上为查找操作增加难度。如果查找的字符是字母就可以通过索引直接找到位置，如果查找的字符是‘.’，就要查找该节点所有next节点。

查找‘.’时，就是遍历某字母下的一整层，直到找到不为NULL的Node继续往下找（为NULL就说明该索引对应的字母不存在）。

此外，这两种情况对于true和false有相反的需求。查找字母时，如果next对应索引元素为NULL，则说明没有该字母，进而整个递归搜索函数可以停止；而如果找到对应的元素，就可以继续往下查。查找'.'时，需要遍历某字母next的所有元素，可能会有false，但是因为比查找字母时存在更多的可能，所以忽略false，重视true。一旦遍历到最后结果是true，就可以停止递归。

	查找字母	查找'.'
时间复杂度	O(1)	O(n)
递归停止	false	true
true和false的出现位置	判断是否存在字母	word[index]='\0'

 

通过以上思考，我写出了递归搜索函数。然而还有一个细节没注意，代码就变得很复杂。递归到最后的判断条件该怎么写？我先前写的是if (word[index+1] == '\0')。后来看别人代码时注意到，一开始进入搜索函数的节点是头节点，搜索第一个字符时节点也是头节点。搜索第二个字符时，第一个字符肯定已找到对应的节点。那么搜索到'\0'时，就到达了对应最后一个字符的Node。此时字符已全都找到，只要判断是否是单词即可。判断条件应是if (word[index] == '\0')，代码如下：

#define LEN 26


typedef struct WordDictionary WordDictionary;

struct WordDictionary {
	bool is_word;
	WordDictionary **next;
};

/** Initialize your data structure here. */

WordDictionary* wordDictionaryCreate() {
	WordDictionary* obj = (WordDictionary*)malloc(sizeof(WordDictionary));
	obj->is_word = false;
	int space = sizeof(WordDictionary*)*LEN;
	obj->next = (WordDictionary**)malloc(space);
	memset(obj->next, 0, space);
	return obj;
}

/** Adds a word into the data structure. */
void wordDictionaryAddWord(WordDictionary* obj, char * word) {
	int i;
	for (i = 0; word[i]; i++) {
		int nIndex = word[i] - 'a';
		if (!(obj->next[nIndex]))
			obj->next[nIndex] = wordDictionaryCreate();
		obj = obj->next[nIndex];
	}
	obj->is_word = true;
}

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */

bool recursiveSearch(WordDictionary *obj, char * word, int index) {
	if (word[index] == '\0') {
		return obj->is_word;
	}

	while (word[index] != '\0') {
		int nIndex = word[index] - 'a';
		if (word[index] != '.')
		{
			if (obj->next[nIndex] != NULL)
				return recursiveSearch(obj->next[nIndex], word, index + 1);
			else
				return false;
		}
		else {
			for (int i = 0; i < LEN; i++) {
				if (obj->next[i]) {
					if (recursiveSearch(obj->next[i], word, index + 1))
						return true;
				}
			}
			return false;
		}
	}
	return NULL;
}

bool wordDictionarySearch(WordDictionary* obj, char * word) {
	return recursiveSearch(obj, word, 0);
}


void wordDictionaryFree(WordDictionary* obj) {
	free(obj->next);
	free(obj);
}

/**
 * Your WordDictionary struct will be instantiated and called as such:
 * WordDictionary* obj = wordDictionaryCreate();
 * wordDictionaryAddWord(obj, word);

 * bool param_2 = wordDictionarySearch(obj, word);

 * wordDictionaryFree(obj);
*/