UVa 11362

UVa 11362

題目

http://domen111.github.io/UVa-Easy-Viewer/?11362

我們有很多手機號碼,但是如果有任何一支手機號碼 $p$ 是另一支手機號碼 $q$ 的前綴

那麼在撥號給 $q$ 的時候會先撥到 $p$ ,導致 $q$ 實質上是一隻無用的號碼

現在給你 $n$ 個手機號碼,請問是否每支號碼都是可行的

想法

要檢查一堆字串是否有前綴相同,最簡單的想法就是先依照字典續排序好

那麼前綴相同的字串就會被排在一起,我們每次都只需要檢查排再一起的連續字串是否相同即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int t, n;
string arr[10010];

bool same_prefix(string p, string q){
for(int i=0, j=0 ; i<p.size() && j<q.size() ; i++, j++){
if(p[i]!=q[j]) return false;
}
return true;
}

int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
bool ans=true;
for(int i=0, j ; i<n-1 && ans ; i++){
if(same_prefix(arr[i], arr[i+1])){
ans = false;
break;
}
}
if(ans) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

每筆測資排序時間複雜度為 $O(nlogn)$

每筆測資檢查前綴的時間複雜度約為 $O(np)$, $p$ 指的是最長的字串長度

總時間複雜度約為 $O(t(n nlogn + np))$