[leetcode]211. Add and Search Word - Data structure design
Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters
a-z
or .
. A .
means it can represent any one letter. For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
class TrieNode{
public:
bool isKey;
TrieNode* children[26];
TrieNode():isKey(false){
memset(children,NULL,sizeof(TrieNode*)*26);
};
};
class WordDictionary {
public:
/** Initialize your data structure here. */
WordDictionary() {
root=new TrieNode();
}
/** Adds a word into the data structure. */
void addWord(string word) {
TrieNode* run=root;
for(char c:word)
{
if(!(run->children[c-'a']))
run->children[c-'a']=new TrieNode();
run=run->children[c-'a'];
}
run->isKey=true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool search(string word) {
return query(word.c_str(),root);
}
private:
TrieNode* root;
bool query(const char* word,TrieNode* node)
{
TrieNode* run=node;
for(int i=0;word[i];i++)
{
if(run && word[i]!='.')
run=run->children[word[i]-'a'];
else if(run && word[i]=='.')
{
TrieNode* tmp=run;
for(int j=0;j<26;j++)
{
run=tmp->children[j];
if(query(word+i+1,run))
return true;
}
}
else
break;
}
return run && run->isKey;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.