참고
문제해설
문제 로직고민
NOTE
•
접두사 검색을 요구하는것 방식은 Trie자료구조로 풀 수 있다.
◦
Trie 자료구조를 구현하고, 전화번호부의 문자열을 모두 넣는다.
◦
이후 번호부의 모든 문자열을 Trie의 search를 진행하고, 해당 문자의 마지막 Node에서 자식노드가 있는지 확인한다.
◦
있으면 Prefix가 존재하는 것이고, 아니면 없다는 것이다.
작성코드
NOTE
class Solution {
public boolean solution(String[] phone_book) {
Trie trie = new Trie();
for(String s : phone_book){
trie.insert(s, trie.root);
}
for(String s : phone_book){
if(trie.prefix(s, trie.root)) return false;
}
return true;
}
}
class Node{
Map<Character, Node> children;
boolean isLast;
Node(){
children = new HashMap();
isLast = false;
}
}
class Trie{
Node root;
Trie(){
root = new Node();
}
public void insert(String s, Node node){
if(s.length() == 0) {
node.isLast = true;
return;
}
char c = s.charAt(0);
if(!node.children.containsKey(c)) node.children.put(c, new Node());
insert(s.substring(1), node.children.get(c));
}
public boolean prefix(String s, Node node){
if(s.length() == 0) {
if(node.children.size() > 0) return true;
else return false;
}
char c = s.charAt(0);
if(!node.children.containsKey(c)) return false;
else return prefix(s.substring(1), node.children.get(c));
}
}
Java
복사
다른사람 풀이
NOTE
class Solution {
public boolean solution(String[] phoneBook) {
for(int i=0; i<phoneBook.length-1; i++) {
for(int j=i+1; j<phoneBook.length; j++) {
if(phoneBook[i].startsWith(phoneBook[j])) {return false;}
if(phoneBook[j].startsWith(phoneBook[i])) {return false;}
}
}
return true;
}
}
Java
복사
가장 간단한 풀이
•
문제 유형이 워낙 Trie에서 유명한 방식이라 다른 방식을 생각하지 않았는데 이 방식도 해결로 쳐주는것 같다.
•
이외의 풀이들도 이와 비슷하게 진행되었으며, Trie가 결국 가장 효율적인 방식인게 맞는것같다.
•
왜 문제 유형이 Hash인지는 잘 모르겠다. Trie도 Map을 쓰니 하나의 해시 테이블이라 보는걸까?