문제
https://leetcode.com/problems/design-add-and-search-words-data-structure/description/?envType=study-plan-v2&envId=top-interview-150
해결 방법 1
- 208. Implement Trie (Prefix Tree) 이 문제의 해결방법과 마찬가지로 Trie를 사용하여 해결
- .이 입력된 경우 .에 a ~ z를 넣어보고 단어가 존재하면 true return
- 시간을 줄이기 위해 .이 2개 이상 있는 경우(문제에선 .이 최대 2개이긴 함) 이전의 .에 특정 알파벳을 넣었을 때, 다음 .이 나오기 전까지의 문자열이 startsWith이 true로 return 되어야 다음 . 진행
- ex) b..을 체크하는 경우 먼저 ba.이 생성 됨 => ba로 시작하는 단어가 있는 경우에만 baa ~ baz를 진행하고 ba로 시작하는 단어가 없는 경우에는 bb.으로 넘어감
코드
class WordDictionary {
private Node root;
public WordDictionary() {
this.root = new Node();
}
public void addWord(String word) {
Node current = this.root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (current.children[idx] == null) {
current.children[idx] = new Node();
}
current = current.children[idx];
}
current.isEndOfWord = true;
}
public boolean search(String word) {
if (!word.contains(".")) {
return detailSearch(word);
} else {
return makeWordAndSearch(word);
}
}
private boolean makeWordAndSearch(String word) {
int dotIdx = word.indexOf(".");
for (char c = 'a' ; c <= 'z' ; c ++) {
String newWord = word.substring(0, dotIdx) + c + word.substring(dotIdx + 1);
if (newWord.contains(".")) {
if (startsWith(newWord.split("\\.")[0])) {
if (makeWordAndSearch(newWord)) {
return true;
}
}
} else {
if (detailSearch(newWord)) {
return true;
}
}
}
return false;
}
static Node current;
public boolean detailSearch(String word) {
if (!startsWith(word)) return false;
return current.isEndOfWord;
}
public boolean startsWith(String prefix) {
current = this.root;
for (char c : prefix.toCharArray()) {
int idx = c - 'a';
if (current.children[idx] == null) return false;
current = current.children[idx];
}
return true;
}
}
class Node {
Node[] children;
boolean isEndOfWord;
Node() {
this.children = new Node[26];
this.isEndOfWord = false;
}
}
결과
- startsWith을 체크하는 로직을 추가하기 전보다 시간이 약 3배 정도 빨라졌지만, 그럼에도 시간적으로 더 효율적인 방법이 있는 것 같다고 생각함
해결 방법 2
- 문자열 'b.d'가 주어졌다고 가정했을 때, 전에는 bad ~ bzd까지 모든 경우를 확인해서 시간이 오래 걸렸다고 생각함
- 이 문제를 해결하기 위해 현재 Node가 b일 때, '.'을 만나게 되는데 이 경우 a~z까지 하나씩 넣는 것이 아닌 현재 Node의 children이 null이 아닌 경우에만 체크하는 방식으로 수정함
- 이전에 bcx, bck, bez가 삽입되었다면, b Node에서 children[c], children[e]만 null이 아니기 때문에 c, e만 체크
- 주의해야 할 점은 'a'만 삽입되어 있고 '.a'를 체크하는 경우를 생각해 보자
- 처음에 .을 만나면 a로 이동하게 됨 (이전에 a가 삽입되어 있기 때문)
- .을 a로 가정한 경우 다음을 체크해야되는데 a 다음은 없음
- 이 경우에 a는 endOfWord이기 때문에 true를 return 하는 문제가 발생했음
- 이를 해결하기 위해 현재 word에서 체크하는 idx와 이전에 체크한 횟수 checkCnt를 추가하여 둘이 다르면 false를 return 하도록 하여 해결
- 위의 상황에서 '.a'는 idx는 2이지만 checkCnt는 1이기 때문에 false return
코드
class WordDictionary {
private Node root;
public WordDictionary() {
this.root = new Node();
}
public void addWord(String word) {
Node current = this.root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (current.children[idx] == null) {
current.children[idx] = new Node();
}
current = current.children[idx];
}
current.isEndOfWord = true;
}
static Node current;
public boolean search(String word) {
current = this.root;
return detailSearch(word, 0, 0);
}
public boolean detailSearch(String word, int startIdx, int checkCnt) {
int idx = startIdx;
for (; idx < word.length() ; idx ++) {
char c = word.charAt(idx);
if (c == '.') {
for (int j = 0 ; j < 26 ; j ++) {
if (current.children[j] != null) {
Node temp = current;
current = current.children[j];
if (detailSearch(word, idx + 1, checkCnt + 1)) {
return true;
}
current = temp;
}
}
} else {
if (current.children[c - 'a'] == null) return false;
current = current.children[c - 'a'];
checkCnt ++;
}
}
if (idx == checkCnt) {
return current.isEndOfWord;
} else {
return false;
}
}
}
class Node {
Node[] children;
boolean isEndOfWord;
Node() {
this.children = new Node[26];
this.isEndOfWord = false;
}
}
결과
- 해결방법 1에 비해 시간을 많이 줄일 수 있었음
