【Trie 字典树】Phone List

#【Trie 字典树】Phone List

。。。记录

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n, m;int vis[N][20], pos = 0;void in(string s) {int len = s.size();int p = 0;for(int i = 0; i < len; i++) {int t = s[i] - '0';if(!vis[p][t]) vis[p][t] = ++pos;p = vis[p][t];}
}bool find(string s) {int len = s.size();int p = 0;for(int i = 0; i < len; i++) {int t = s[i] - '0';if(!vis[p][t])return false;p = vis[p][t];}return true;
}
string a[N];
int main() {cin >> n;for(int i = 0; i < n; i++) {pos = 0;memset(vis, 0, sizeof(vis));//重置需要的数组int m;cin >> m;for(int j = 0; j < m; j++) {cin >> a[j];}sort(a, a + m);bool flag = true;for(int j = m - 1; j >= 0; --j) {if(find(a[j])) {flag = false;break;}in(a[j]);}if(flag) cout<<"YES\n";else cout<<"NO\n";}return 0;
}