문제 먼저 읽기
- 새 단어를 추가하거나 추가한 단어와 일치하는 문자열을 찾을 수 있는 데이터 구조를 구현해봅시다.
- WordDictionary() 객체를 초기화합니다.
- void addWord(word) 데이터 구조에 단어를 추가하며, 나중에 일치시킬 수 있습니다.
- void search(word) 데이터 구조에 단어와 일치하는 문자열이 있으면 참을 반환하고 그렇지 않으면 거짓을 반환합니다. 단어는 점 '.'을 포함할 수 있으며, 여기서 점은 어떤 문자와도 일치할 수 있습니다.
어떻게 풀까?
생각
- Trie 를 다시한번 구현해봅시다. 어제 풀었던 문제라 생각보다 바로 수도코드를 작성할 수 있었습니다.
- . 이 나오는 경우에는 모든 문자를 검색할 수 있도록 합니다.
수도코드
class WordDictionary {
Node root;
public WordDictionary() {
this.root = new Node();
}
public void addWord(String word) {
addWord(this.root, word);
}
public void addWord(Node node, String word) {
if (word.length() ==0) {
node.isEndOfWord = true;
return;
}
char c = word.charAt(0);
node.children[c-'a'] = new Node();
addWord(node.children[c-'a'], word.substring(1));
}
public boolean search(String word) {
return search(this.root, word);
}
public boolean search(Node node, String word) {
if (node == null) {
return false;
}
if (word.length() ==0) {
if (node.isEndOfWord) return true;
return false;
}
char c = word.charAt(0);
if (c == '.') { // 이부분이 바뀌었습니다.
for (int i=0; i<26; i++) {
if (search(node.children[i], word.substring(1))) {
return true;
}
}
return false;
} else {
if (node.children[c-'a'] == null) {
return false;
}
}
return search(node.children[c-'a'], word.substring(1));
}
}
class Node {
Node[] children;
boolean isEndOfWord;
public Node() {
this.children = new Node[26];
this.isEndOfWord = false;
}
}
- 위 코드에서 자꾸 NullPointException 가 나서 고치다보니 if로 중첩된 코드를 짜게 되었습니다. 그래서 다시 경우의 수를 점검하며 리팩토링하던 중 String을 매번 자르는 것이 아니라 Index 변수를 추가하여 메모리 효율을 높일 수 있었습니다.
class WordDictionary {
Node root;
public WordDictionary() {
this.root = new Node();
}
public void addWord(String word) {
addWord(this.root, word, 0);
}
public void addWord(Node node, String word, int index) {
if (word.length() == index) {
node.isEndOfWord = true;
return;
}
char c = word.charAt(index++);
if(node.children[c-'a'] == null) {
node.children[c-'a'] = new Node();
}
addWord(node.children[c-'a'], word, index);
}
public boolean search(String word) {
return search(this.root, word, 0);
}
public boolean search(Node node, String word, int index) {
if (node==null) return false;
if (word.length() == index) {
return node.isEndOfWord;
}
char c = word.charAt(index++);
if (c == '.') {
for (int i=0; i<26; i++) {
if (search(node.children[i], word, index)) {
return true;
}
}
return false;
}
if (node.children[c-'a'] == null) {
return false;
}
return search(node.children[c-'a'], word, index);
}
}
class Node {
Node[] children;
boolean isEndOfWord;
public Node() {
this.children = new Node[26];
this.isEndOfWord = false;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
결과
<aside> 👉🏻 Success
Runtime: 155 ms, faster than 92.80% of Java online submissions for Design Add and Search Words Data Structure.
Memory Usage: 91.9 MB, less than 84.15% of Java online submissions for Design Add and Search Words Data Structure.
</aside>
다른 풀이 방식과 문제 회고
- sample 144 ms submission
class TrieNode{
public boolean isEnd;
public TrieNode[] children;
public TrieNode(){
isEnd = false;
children = new TrieNode[26];
}
}
class WordDictionary {
public TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
TrieNode cur = root;
int i = 0;
while(i < word.length()){ // 재귀가 아니라 반복문으로 구현하는 방법도 있습니다.
char ch = word.charAt(i);
if(cur.children[ch-'a'] == null){
cur.children[ch-'a'] = new TrieNode();
}
cur = cur.children[ch-'a'];
i++;
}
cur.isEnd = true;
}
public boolean search(String word) {
return searchHelper(word,0,root);
}
public boolean searchHelper(String word, int index, TrieNode cur){
if(index == word.length())
return cur.isEnd;
char ch = word.charAt(index);
if(ch == '.'){
for(TrieNode node : cur.children){
if(node!=null && searchHelper(word, index+1, node)){
return true;
}
}
return false;
}
else{
TrieNode node = cur.children[ch-'a'];
if(node == null)
return false;
return searchHelper(word, index+1, node);
}
}
}
