AcWing 161. Java 电话列表
原题链接
简单
作者:
ACSaber
,
2020-11-30 12:47:28
,
所有人可见
,
阅读 458
import java.util.*;
import java.io.*;
class Main {
static int N = 100009;
static int[][] trie;
static int[] count;
static int idx;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(reader.readLine());
for (int i = 0; i < t; i++) {
trie = new int[N][10];
count = new int[N];
idx = 0;
int n = Integer.parseInt(reader.readLine());
int[][] arr = new int[n][11];
for (int j = 0; j < n; j++) {
String[] s = reader.readLine().split("");
// System.out.println(Arrays.toString(s));
int len = s.length;
int[] ints = new int[len];
for (int k = 0; k < len; k++) {
ints[k] = Integer.parseInt(s[k]);
}
arr[j] = ints;
}
// sort:将数组长度小的排在前面,长度相同的则无所谓
Arrays.sort(arr, (int[] a, int[] b) -> {
int aLen = a.length;
int bLen = b.length;
if (aLen == bLen) {
return 0;
} else {
return aLen > bLen ? 1 : -1;
}
});
boolean b = insert(arr);
writer.write(b ? "YES" : "NO");
writer.write("\n");
}
reader.close();
writer.flush();
writer.close();
}
private static boolean insert(int[][] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int[] ints = arr[i];
// System.out.println(Arrays.toString(ints));
int len = ints.length;
int p = 0;
for (int j = 1; j <= len; j++) {
int u = ints[j - 1];
if (trie[p][u] != 0) {
if (count[trie[p][u]] != 0) return false;
} else {
trie[p][u] = ++idx;
}
p = trie[p][u];
}
count[p]++;
}
return true;
}
}