M04089 电话号码

思路：

• 建立 Trie 树，插入一个字符串时需要检查是否存在存在其前缀或后缀。
• 对于“前缀”，只需在每个节点上记录 end 表示是否存在以之结尾的字符串；对于后缀，只需记录当前字符串结尾的 Trie 节点是否为新增的节点即可。

#include <stdio.h>
#include <string.h>

struct Node {
	bool end;
	int nxt[10];
	
	void clear(){
		end = false;
		for (int i = 0; i <= 9; i++){
			nxt[i] = 0;
		}
	}
};

int id;
char phone[12];
Node tree[100002];

void init(){
	id = 0;
	tree[0].clear();
}

bool insert(char s[]){
	int len = strlen(&s[1]), x = 0;
	bool nsuffix, nprefix = true;
	for (int i = 1; i <= len; i++){
		int ch = s[i] - '0';
		if (i == len) nsuffix = tree[x].nxt[ch] == 0;
		if (tree[x].nxt[ch] == 0){
			id++;
			tree[x].nxt[ch] = id;
			tree[id].clear();
		}
		x = tree[x].nxt[ch];
		nprefix &= !tree[x].end;
	}
	tree[x].end = true;
	return nprefix && nsuffix;
}

int main(){
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++){
		int n;
		bool ans = true;
		scanf("%d", &n);
		init();
		for (int j = 1; j <= n; j++){
			scanf("%s", &phone[1]);
			ans &= insert(phone);
		}
		if (ans){
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}