- str是前i个已插入字符串的前缀
- 前i个已插入的字符串中存在str的前缀
对于1,对应code中lens==len(char),因为在插入过程中没有建立新节点,即一直在else:lens+=1中。
对于2,对应code中ed[q]非0,因为在插入过程中遇到了之前插入的终点即(终点有ed[q]+=1)
def insert(char):
global idx
q=0
lens=0 #记录长度
for i in range(len(char)):
u=ord(char[i])-ord('0')
if not Trie[q][u]:
idx+=1
Trie[q][u]=idx
else: #如果一直没建立新节点,即一直进入的是lens+=1,则最后lens和char长度相等
lens+=1
q=Trie[q][u]
if ed[q] or lens==len(char):
return True #因为是直接能判断出NO,所以直接返回不用进行后续的程序执行
ed[q]+=1
return False
t = int(input())
for _ in range(t):
Trie = [[0] * 10 for i in range(100000)]
ed = [0] * 100000 #每个测试用例初始化Trie,
idx = 0 #防止不同的测试用例的Trie相互干扰
ans=[] #记录字符串,为了减少字符串进入Trie
n=int(input())
for i in range(n):
im=input()
ans.append(im)
for i in ans:
if insert(i): #只要有,就不用后续的判断了
print('NO')
break
else:
print('YES')