2023每日刷题（二十）

POJ-3630电话表

题目原地址

输入样例：

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

输出结果：

NO
YES

实现代码

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
// 最多10000个字符串
const int maxn=100005;
// 不同字符个数
const int maxz=10;
int trie[maxn][maxz];
bool endd[maxn];
int n, tot;bool insertt(string s) {int len = s.length(), p = 1;for(int i = 0; i < len; i++) {int ch = s[i] - '0';if(!trie[p][ch]) {trie[p][ch] = ++tot;// 字符串处理完毕，仍不为空，说明该串是其他串的前缀} else if(i == len - 1) {return true;}p = trie[p][ch];if(endd[p]) {return true;}}endd[p] = true;return false;
}int main() {int T;bool ans;string s;cin >> T;// 测试用例个数while(T--) {memset(trie, 0, sizeof(trie));memset(endd, false, sizeof(endd));tot = 1;ans = false;// 电话号码个数cin >> n;for(int i = 1; i <= n; i++) {cin >> s;if(ans) {continue;}if(insertt(s)) {ans = true;}}if(ans) {cout<< "NO"<< endl;} else {cout << "YES"<< endl;}}return 0;
}

样例运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！