04089: 电话号码

trie, http://cs101.openjudge.cn/practice/04089/

给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：

Emergency 911 Alice 97 625 999 Bob 91 12 54 26

在这个例子中，我们不可能拨通Bob的电话，因为Emergency的电话是它的前缀，当拨打Bob的电话时会先接通Emergency，所以这些电话号码不是一致的。

输入

第一行是一个整数t，1 ≤ t ≤ 40，表示测试数据的数目。每个测试样例的第一行是一个整数n，1 ≤ n ≤ 10000，其后n行每行是一个不超过10位的电话号码。

输出

对于每个测试数据，如果是一致的输出“YES”，如果不是输出“NO”。

样例输入

样例输出

NO
YES

04089:电话号码。使用方法二（直接比较）作为首选，因为实现简单且在Python中对于题目给出的数据规模（n≤10000）效率足够。当处理更大规模数据时，则应选择Trie实现（方法一）。方法一：Trie（字典树）实现，方法二：排序后直接比较。即更简单的方法是对号码排序后逐个检查是否为前缀。方法三：递归字典实现。另一种Trie的递归实现方式。

方法一：

要解决这个问题，需要判断是否存在某个电话号码是另一个电话号码的前缀。这可以通过构建一个 字典树（Trie） 来高效实现。

解题思路

字典树（Trie）：
- 字典树是一种专门用来处理字符串前缀问题的数据结构。
- 每个节点存储一个字符，路径表示字符串的前缀。
- 如果某个节点已经是某个电话号码的结尾（即完整电话号码），那么后续插入的任何电话号码都会以它为前缀。
算法步骤：
- 对于每个测试样例：
  1. 构建一个空的字典树。
  2. 将所有电话号码按长度从短到长排序（因为短的号码更可能是长号码的前缀）。
  3. 遍历每个电话号码：
    - 在字典树中查找该号码是否已经存在完整的前缀。
    - 如果存在，则直接输出 "NO"。
    - 否则，将该号码插入字典树。
  4. 如果所有号码都成功插入且没有冲突，输出 "YES"。
复杂度分析：
- 插入和查找操作在字典树中的时间复杂度为 $O (L)$ ，其中 L 是电话号码的长度。
- 因此，总的时间复杂度为 $O (t \cdot n \cdot L)$ ，其中 t 是测试样例数，n 是电话号码的数量，L 是电话号码的最大长度。

实现代码

python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_number = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, number):
        node = self.root
        for digit in number:
            if digit not in node.children:
                node.children[digit] = TrieNode()
            node = node.children[digit]
            # 如果当前节点已经是某个电话号码的结尾，则说明存在前缀冲突
            if node.is_end_of_number:
                return False
        # 插入完成后，标记为完整电话号码
        node.is_end_of_number = True
        # 如果当前节点还有子节点，说明有其他号码以它为前缀
        return len(node.children) == 0
    
    def is_consistent(self, numbers):
        # 按长度从短到长排序，确保短号码先被检查
        numbers.sort(key=len)
        for number in numbers:
            if not self.insert(number):
                return False
        return True

def main():
    import sys
    input = sys.stdin.read
    data = input().splitlines()
    
    t = int(data[0])  # 测试样例数量
    index = 1
    results = []
    
    for _ in range(t):
        n = int(data[index])  # 当前测试样例的电话号码数量
        index += 1
        numbers = data[index:index + n]
        index += n
        
        trie = Trie()
        if trie.is_consistent(numbers):
            results.append("YES")
        else:
            results.append("NO")
    
    print("\n".join(results))

# 调用主函数
if __name__ == "__main__":
    main()

代码解释

TrieNode 类：
- children：存储子节点，键是数字字符，值是子节点对象。
- is_end_of_number：标记当前节点是否是一个完整电话号码的结尾。
Trie 类：
- insert 方法：在字典树中插入一个电话号码，同时检查是否存在前缀冲突。
- is_consistent 方法：遍历所有电话号码，依次插入字典树，返回是否一致。
主函数：
- 读取输入数据，解析测试样例。
- 对每个测试样例调用 Trie 的 is_consistent 方法，输出结果。

注意事项

输入电话号码可能包含前导零，因此不能将其转换为整数。
排序电话号码时按照长度从小到大排序，可以减少不必要的冲突检查。
使用字典树能够高效地解决前缀问题，避免暴力比较的高时间复杂度。

最优解（不需要Trie）：排序+相邻比较。排序后所有前缀关系只可能出现在相邻元素之间。

python

t = int(input())
for _ in range(t):
    n = int(input())
    nums = [input().strip() for _ in range(n)]
    nums.sort()                           # 字典序排序

    ok = True
    for i in range(n-1):
        # 如果前一个是后一个的前缀 → 冲突
        if nums[i+1].startswith(nums[i]):
            ok = False
            break

    print("YES" if ok else "NO")

https://www.geeksforgeeks.org/trie-insert-and-search/

Definition: A trie (prefix tree, derived from retrieval) is a multiway tree data structure used for storing strings over an alphabet. It is used to store a large amount of strings. The pattern matching can be done efficiently using tries.

Trie思路，逻辑：

插入号码时，如果你的路径上遇到“终止标记”，则表示已有短号码是你的前缀 → 冲突
插入完毕后，如果你自己是前缀（有子节点）→ 冲突

⚠️：如果有重复号码存在，→ 冲突

python

class Node:
    def __init__(self):
        self.child = {}
        self.end = False

def insert(root, s):
    cur = root
    for c in s:
        # 如果在路径上遇到已结束的号码，说明已有短号码是当前号码的前缀 -> 冲突
        if cur.end:
            return False
        if c not in cur.child:
            cur.child[c] = Node()
        cur = cur.child[c]
    # 到达末尾：若这个节点已有结束标记，说明完全相同的号码已存在 -> 冲突
    if cur.end:
        return False
    # 若这个节点有子节点，说明当前号码是已有更长号码的前缀 -> 冲突
    if cur.child:
        return False
    cur.end = True
    return True

import sys
input = sys.stdin.readline

t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    nums = [input().strip() for _ in range(n)]
    nums.sort()  # 升序排序（短的前面）

    root = Node()
    ok = True
    for num in nums:
        if not insert(root, num):
            ok = False
            break
    print("YES" if ok else "NO")

使用字典实现的字典树（Trie）。它的主要功能是插入和搜索字符串。

这里特意把 insert 和 search 分开写，也是保留了Trie本身的完整性。

python

class TrieNode:
    def __init__(self):
        self.child={}


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, nums):
        curnode = self.root
        for x in nums:
            if x not in curnode.child:
                curnode.child[x] = TrieNode()
            curnode=curnode.child[x]

    def search(self, num):
        curnode = self.root
        for x in num:
            if x not in curnode.child:
                return 0
            curnode = curnode.child[x]
        return 1


t = int(input())
p = []
for _ in range(t):
    n = int(input())
    nums = []
    for _ in range(n):
        nums.append(str(input()))
    nums.sort(reverse=True)
    s = 0
    trie = Trie()
    for num in nums:
        s += trie.search(num)
        trie.insert(num)
    if s > 0:
        print('NO')
    else:
        print('YES')

python

# 雷逸鸣 物理学院
class Solution:
    def is_consistent(self, phone_numbers):
        phone_numbers.sort()  # 对电话号码列表进行排序
        for i in range(len(phone_numbers) - 1):
            if phone_numbers[i + 1].startswith(phone_numbers[i]):
                return False
        return True

def main():
    t = int(input().strip())
    for _ in range(t):
        n = int(input().strip())
        phone_numbers = [input().strip() for _ in range(n)]
        solution = Solution()
        if solution.is_consistent(phone_numbers):
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    main()

方法三：递归字典实现。是另一种Trie的递归实现方式。

用字典嵌套建树，按照每一位数字，如果是子节点就在子节点继续添加，如果不是就新建子节点，在此添加，最后记录end；遍历的时候按深度优先，如果end和其他节点同时存在，就是NO

python

# 赵新坤 物理学院
def trav(adct,i):
    ans=[]
    kys=[k for k in adct.keys()]
    if 'end' in kys and len(kys)>1:
        ans.append('NO')
    for key in adct.keys():
#        print('     '*i+key)
        if adct[key]:
            ans.extend(trav(adct[key],i+1))
    return ans
def insert(alst,adct):
    p=alst.pop(0)
    if p not in adct.keys():
        adct[p]={}
    if alst:    
        adct[p]=insert(alst,adct[p])
    else :
        adct[p].update({'end':None })
    return adct
t=int(input())
anslst=[]
for _ in range(t):
    n=int(input())
    tree={}
    ans='YES'
    num_set=set()
    for i in range(n):
        ipt=str(input())
        if ipt in num_set:
            ans='NO'
        num_set.add(ipt)
        ipt_num_lst=[x for x in ipt]
        tree=insert(ipt_num_lst,tree)
    if 'NO' in trav(tree,0):
        ans='NO'
    anslst.append(ans)
for i in anslst:
    print(i)

python

def insert(phone, node):
    for i, digit in enumerate(phone):
        if 'end' in node:
            # 当前路径已经是某个号码的结尾，但我们还在往下走，说明前缀冲突
            return False
        if digit not in node:
            node[digit] = {}
        node = node[digit]
    # 插入结束，如果这个节点还有子节点，说明有其他号码以它为前缀
    if node:
        return False
    node['end'] = None
    return True

t = int(input())
for _ in range(t):
    n = int(input())
    numbers = [input().strip() for _ in range(n)]
    tree = {}
    consistent = True
    for num in sorted(numbers):  # 先排序，前缀更容易被检测出来
        if not insert(num, tree):
            consistent = False
            break
    print("YES" if consistent else "NO")

【蔡东辰、24工学院】只记得字典树是字典套字典，但课件里的代码只是粗略扫了一眼，没记住具体怎么写，于是自己想了一个。对于这题而言，通过递归计算总叶子节点数量，如果与输入的数据数量不一致就输出NO。但是一开始写的时候一直wa，和ai共同探索后才发现number里的数据一开始以int形式存了，导致有先导0时会出错，去了int之后果然ac了，感觉是值得进我错题本的题

python

class Trie:
    def __init__(self,key = None):
        self.dic = {}
        self.key = key
    def add(self,s):
        if s[0] not in self.dic:
            self.dic[s[0]] = Trie(s[0])
        a = self.dic[s[0]]
        if len(s) > 1:
            a.add(s[1:])
    def leaf_nums(self):
        if len(self.dic) == 0:
            return 1
        num = 0
        for i in self.dic:
            num += self.dic[i].leaf_nums()
        return num
t = int(input())
for i in range(t):
    n = int(input())
    trie = Trie()
    number = []
    for j in range(n):
        number.append(input())
    number.sort(key = lambda x:-len(x))
    for k in number:
        trie.add(str(k))
    if trie.leaf_nums() == n:
        print('YES')
    else:
        print('NO')

04089: 电话号码 ​

04089: 电话号码