LeetCode Add and Search Word - Data structure design
7703 단어 LeetCode
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
Note:You may assume that all words are consist of lowercase letters
a-z
. 매번
class CharNode {
public:
int count;
CharNode* child[26];
CharNode(int cnt = 0) : count(cnt) {
for (int i = 0; i<26; i++) {
child[i] = NULL;
}
}
};
class WordDictionary {
private:
CharNode root;
void add(const string& str) {
CharNode* current = &root;
int pos = 0;
int len = str.size();
char ch;
while (pos < len) {
ch = str[pos] - 'a';
if (current->child[ch] == NULL) {
current->child[ch] = new CharNode();
}
if (pos == len - 1) {
current->child[ch]->count++;
}
current = current->child[ch];
pos++;
}
}
bool dfs_search(CharNode* at, string& word, int pos) {
if (at == NULL) {
return false;
}
int len = word.size();
if (len == pos && at != NULL && at->count > 0) {
return true;
} else if (pos >= len) {
return false;
}
if (word[pos] == '.') {
// wildcard
for (int i=0; i<26; i++) {
if (dfs_search(at->child[i], word, pos + 1)) {
return true;
}
}
} else {
return dfs_search(at->child[word[pos] - 'a'], word, pos + 1);
}
return false;
}
public:
WordDictionary() {
// placeholder for '\0' string
root.count = 1;
}
// Adds a word into the data structure.
void addWord(string word) {
add(word);
}
// 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 dfs_search(&root, word, 0);
}
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.