LeetCode 211 - Add and Search Word - Data structure design
2655 단어 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
. public class WordDictionary {
public static class TrieNode {
TrieNode[] children;
boolean isLeaf;
public TrieNode() {
children = new TrieNode[26];
}
}
private TrieNode root = new TrieNode();
// Adds a word into the data structure.
public void addWord(String word) {
if(word == null || word.isEmpty()) return;
TrieNode node = root;
for(int i=0; i<word.length(); i++) {
int j = word.charAt(i)-'a';
if(node.children[j] == null) {
node.children[j] = new TrieNode();
}
node = node.children[j];
}
node.isLeaf = true;
}
// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
public boolean search(String word) {
return search(root, word, 0);
}
private boolean search(TrieNode node, String word, int start) {
if(node == null) return false;
if(start == word.length()) return node.isLeaf;
for(int i=start; i<word.length(); i++) {
char c = word.charAt(i);
if(c == '.') {
for(int j=0; j<26; j++) {
if(search(node.children[j], word, i+1)) return true;
}
return false;
} else {
// node = node.children[c-'a'];
// if(node == null) return false;
return search(node.children[c-'a'], word, i+1);
}
}
return false;//node.isLeaf;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.