https://programmers.co.kr/learn/courses/30/lessons/42577
문자열 배열에서 한 문자열이 다른 문자열의 prefix인 경우가 있는지 확인하는 문제이다.
public boolean solution(String[] phone_book) {
Arrays.sort(phone_book);
for (int i=0; i<phone_book.length-1; ++i) {
if (phone_book[i+1].startsWith(phone_book[i]))
return false;
}
return true;
}
public boolean solution1(String[] phone_book) {
HashSet<String> set = new HashSet<String>(Arrays.asList(phone_book));
for (String num : phone_book) {
for (int i=1; i<num.length(); ++i) {
String sub = num.substring(0, i);
if (set.contains(sub))
return false;
}
}
return true;
}
private static class Node {
Node[] next;
Node(boolean isLeaf) {
next = isLeaf ? null : new Node[10];
}
Node add(int c, boolean isLeaf) {
if (next[c] == null) {
next[c] = new Node(isLeaf);
return next[c];
} else {
// added "12" and add "1"
if (isLeaf)
return null;
// added "12" and add "12..."
else if (next[c].next == null)
return null;
else
return next[c];
}
}
}
public boolean solution(String[] phone_book) {
Node root = new Node(false);
for (String num : phone_book) {
Node cur = root;
for (int i=0; i<num.length(); ++i) {
cur = cur.add(num.charAt(i) - '0', i==num.length()-1);
if (cur == null)
return false;
}
}
return true;
}