0211. Add and Search Word - Data structure design (M)
Add and Search Word - Data structure design (M)
제목.
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. 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
. 제목의 뜻
단어 삽입과 검색 두 가지 동작을 지원하는 데이터 구조를 설계합니다.여기서 검색 단어의 매개 변수는 와일드카드 문자를 포함할 수 있습니다."의 정규.
사고의 방향
0208.사전 트리는 Implement Trie(Prefix Tree)(M)처럼 사용됩니다.다른 점은 검색 문자가'.'인 경우에서 나타나는 모든 문자를 찾습니다.
코드 구현
Java
class WordDictionary {
Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
Node p = root;
for (char c : word.toCharArray()) {
if (p.children[c - 'a'] == null) {
p.children[c - 'a'] = new Node();
}
p = p.children[c - 'a'];
}
p.end = 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(word, 0, root);
}
private boolean search(String word, int index, Node p) {
if (index == word.length()) {
return p.end;
}
char c = word.charAt(index);
if (c == '.') {
for (Node next : p.children) {
if (next != null && search(word, index + 1, next)) {
return true;
}
}
return false;
} else {
return p.children[c - 'a'] != null ? search(word, index + 1, p.children[c - 'a']) : false;
}
}
}
class Node {
Node[] children = new Node[26];
boolean end;
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary(); obj.addWord(word); boolean param_2
* = obj.search(word);
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.