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
| #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))$