「Phone List」电话列表

题目描述

给定 $t$ 组数据，每组给出 $n$ 个仅由数字组成的电话号码（每个不超过 10 位）；若存在某个号码是另一个号码的前缀，列表不兼容，输出 NO，否则输出 YES。输入：第一行整数 $t$ ，每组数据第一行整数 $n$ ，接下来 $n$ 行每行一个号码。范围： $1 \le t \le 40$ ， $1 \le n \le 10000$ 。样例一：输入 911、97625999、91125426，输出 NO（911 是 91125426 的前缀）；样例二：输入 113、12340、123440、12345、98346，输出 YES。

思路

把每个号码逐字符插入 Trie，并在末尾额外走一个哨兵字符（数字里不存在的编号），让“某号码在此终止”也变成一条边；插入途中若发现下一个节点已挂着哨兵（更早的号码在此终止），或走到末尾时节点仍有后继（更早的号码从这里延伸下去），就说明存在前缀关系，输出 NO。每个字符只处理一次，单组复杂度为号码总长 $O(L)$ ，与插入顺序无关，一趟插入即可判定。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 12:28
# update_at: 2026-10-01 12:28

import sys

END = "\x00"  # 哨兵字符：拼在号码末尾，表示“某个号码在此终止”


def is_prefix_free(numbers: list[str]) -> bool:
    """号码集合里是否两两互不为前缀（一个都不出现在另一个开头）。"""
    sons: list[dict[str, int]] = [{}]  # sons[i]：第 i 个节点的子节点表，字符 → 节点编号
    for number in numbers:
        node = 0
        for ch in number + END:  # 补一个终止哨兵，让“前缀”也拥有自己的终点
            if ch == END and sons[node]:  # 最后一位仍有后继 → 当前号码是更早号码的前缀
                return False
            son = sons[node].get(ch)
            if son is None:  # 惰性建点：先在父节点登记，再追加节点本身，编号才不会越过列表末尾
                son = sons[node][ch] = len(sons)
                sons.append({})
            elif END in sons[son]:  # 已有号码在这位终止 → 它是当前号码的前缀
                return False
            node = son
    return True


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    t = int(next(data))

    for _ in range(t):
        n = int(next(data))
        numbers = [next(data).decode() for _ in range(n)]
        verdict = "YES" if is_prefix_free(numbers) else "NO"  # 兼容 = 无前缀关系
        out.append(verdict)

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:40
 * update_at: 2026-10-06 11:42
 */
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

typedef long long ll;

// Trie：sons[node][c] 表示节点 node 沿字符 c 走到的子节点编号，0 表示不存在
const int MAXNODE = 400005; // 每组最多 n*11 个字符，节点数不超过总字符数
int sons[MAXNODE][11];      // 子节点表：0~9 为数字，10 为哨兵 '$'
int node_cnt;               // 当前已用节点数（含根 0）

// 每组数据开始前清空 Trie（只清实际用到的部分）
void trie_init() {
    node_cnt = 1; // 根节点编号 0
    memset(sons[0], 0, sizeof(sons[0]));
}

// 插入号码 s（末尾隐含哨兵 '$'），途中检测前缀冲突；有冲突返回 false
bool trie_insert(const string &s) {
    int node = 0;
    int len = s.size(); // 先存成 int，避免和有符号下标比较出问题
    for (int i = 0; i <= len; i++) {
        int c = (i == len) ? 10 : s[i] - '0'; // 末尾多走一步：哨兵 '$' 用编号 10
        bool has_son = false; // 节点 node 是否已有任何子节点
        for (int k = 0; k < 11; k++)
            if (sons[node][k]) has_son = true;
        if (c == 10 && has_son) return false; // 结尾仍有后继：当前号码是更早号码的前缀
        if (sons[node][c] == 0) { // 惰性建点（含哨兵位）
            sons[node][c] = node_cnt;
            memset(sons[node_cnt], 0, sizeof(sons[node_cnt]));
            node_cnt++;
        } else if (sons[sons[node][c]][10] != 0) {
            // 下一个节点已有哨兵：有号码在这位终止，它是当前号码的前缀
            return false;
        }
        node = sons[node][c];
    }
    return true;
}

int t = 0, n = 0;
string s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n;
        trie_init();
        bool ok = true; // 兼容 = 任意两个号码互不为前缀
        for (int i = 1; i <= n; i++) {
            cin >> s;
            if (ok && !trie_insert(s)) ok = false; // 已判 NO 也要读完剩余输入
        }
        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}