ZOJ 2876 Phone list

ZOJ :: Problems :: Show Problem

問題

n個の文字列が与えられる。ある文字列が、もう一方の文字列のprefixになるような２つの文字列が存在するか判定する。

解法

O(n^2)の全探索だと間に合わない。sortして隣り合う文字列を調べるとo(nlogn)で判定できる。

コード

int main(){
  int T,n;
  cin>>T;
  while(T--){
    cin>>n;
    vector<string> nums(n);
    REP(i,n){
      cin>>nums[i];
    }
    bool ans = true;
    sort(nums.begin(),nums.end());
    REP(i,n-1){
      int j = i+1;
      if(nums[i].size() <= nums[j].size() && 
          nums[i] == nums[j].substr(0,nums[i].size())){
        ans = false;
        goto PRINT;
      }
    }
PRINT:
    if(ans)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
  return 0;
}