Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-12-26

SRM391 Div1 Easy: IsomorphicWords

| 09:42 | SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder のブックマークコメント

問題を読み違えていて問題文のTest Caseすら通らず焦る。

最初はインデックスを作ろうとしていたが、比較がややこしいので総当たりに変更。

class IsomorphicWords {
  int l;
  bool isomor(string w1, string w2){
    vector<int> oc(26,-1);
    rep(i,l){
      int a=w1[i]-'a', b=w2[i]-'a';
      if (oc[a]<0) oc[a]=b;
      else if (oc[a]!=b) return false;
    }
    vector<int> ck(26,0);
    rep(i,26) {
      if (oc[i]<0) continue;
      if (++ck[oc[i]] > 1) return false;
    }
    return true;
  }
public:
  int countPairs(vector<string> words) {
    int n=sz(words); //2-50
    l=words[0].length();
    int count=0;
    for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++) {
        if (isomor(words[i], words[j])) count++;
      }
    }
    return count;
  }
};