참고
문제해설
NOTE
•
단어를 추가/검색 하는 데이터 구조를 구현한다.
•
위의 문구만 보면 단순히 Map을 말하는건가 싶지만 .이라는 와일드카드 문자는 어떠한 문자와도 대칭이 된다.
문제 로직고민
NOTE
•
해당 문제 주제를 몰랐다면 상당히 고민을 했겠지만 Trie를 사용해야하는걸 아니 쉽게 방법이 보이는것 같다.
◦
기존 Trie자료구조에서 .이 나오는경우, 자식 노드를 모두 탐색시키면 된다.
•
위의 방식대로 Search를 구현했는데 해결해야할 요소가 많다.
1.
기존의 for문 방식으로는 .이 나오는경우 구현이 힘드므로 재귀로 변경했다.
2.
.이 나올때 탐색할 Node가 없는경우는 검색에 실패해야한다.
3.
기존 함수에 재귀함수를 추가하는 형식이라 결과값을 저장할 전역변수를 사용해야했다.
4.
전역변수는 예상치 못한 결과를 만들어내므로, true의 변화에대해만 체크하고 재귀가 끝나면 다시 false로 돌려놓았다.
◦
생각보다 재귀로 작성하는게 까다로웠고, 시간이 오래 걸렸다 재귀코드에 대한 연습이 더 필요한것 같다. (대략 30분걸림)
작성코드
NOTE
class WordDictionary {
Node root;
boolean result;
public WordDictionary() {
root = new Node();
result = false;
}
public void addWord(String word) {
addWord(word, root);
}
private void addWord(String word, Node node){
if(word.length() == 0){
node.isLast = true;
return;
}
char start = word.charAt(0);
int idx = start - 'a';
if(node.children[idx] == null) node.children[idx] = new Node();
addWord(word.substring(1), node.children[idx]);
}
public boolean search(String word) {
return search(word, root);
}
// 재귀작성 부분 (핵심로직)
private boolean search(String word, Node node) {
if (word.length() == 0) {
return node.isLast;
}
char start = word.charAt(0);
int idx = start - 'a';
if (start == '.') {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null && search(word.substring(1), node.children[i])) {
return true;
}
}
return false;
} else {
if (node.children[idx] == null) return false;
return search(word.substring(1), node.children[idx]);
}
}
}
class Node{
Node[] children;
boolean isLast;
Node(){
children = new Node[26];
isLast = false;
}
}
Java
복사
재귀 작성에 상당히 애를 먹었다.. 연습이 더 필요해 보인다
정답코드
NOTE
class WordDictionary {
private TrieNode root;
class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() { children = new TrieNode[26]; }
}
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
if (curr.children[c - 'a'] == null) curr.children[c - 'a'] = new TrieNode();
curr = curr.children[c - 'a'];
}
curr.isEnd = true;
}
// 핵심 로직
private boolean helper(String word, TrieNode node, int curr) {
if (curr == word.length()) return node.isEnd;
char c = word.charAt(curr);
if (c != '.') {
if (node.children[c - 'a'] == null) return false;
return helper(word, node.children[c - 'a'], curr + 1);
}
for (int i = 0; i < 26; i++) {
if (node.children[i] != null && helper(word, node.children[i], curr + 1)) return true;
}
return false;
}
/** 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 helper(word, root, 0);
}
}
Java
복사
실행시간이 더 빠른 코드
•
문자열을 자르지 않고, curr이라는 idx변수를 따로 둔점이 실행 속도를 빠르게 해준것같다.
•
로직은 크게 차이가 없는것 같다.