問題
http://community.topcoder.com/stat?c=problem_statement&pm=8175&rd=11125
解き方
全ての文字について、可能な限り昇順になるように変換する。
変換後、一致する文字列群について組み合わせを計算してあげればよい。
コード
class IsomorphicWords {
public: int countPairs(vector<string> words) {
int n=words.size();
FORE(i,0,n){
char ch='a';
FORE(j,0,words[i].size()){
if(words[i][j]==ch)ch++;
else if(words[i][j]>ch){
char prev=words[i][j];
FORE(k,j,words[i].size()){
if(words[i][k]==ch)words[i][k]=prev;
else if(words[i][k]==prev)words[i][k]=ch;
}
ch++;
}
}
}
int ret=0;
int used[n];
memset(used,0,sizeof(used));
FORE(i,0,n)if(used[i]==0){
int cnt=0;
FORE(j,i,n)if(used[j]==0 && words[i]==words[j]){
used[j]=1,cnt++;
}
ret+=cnt*(cnt-1)/2;
}
return ret;
}
};
public: int countPairs(vector<string> words) {
int n=words.size();
FORE(i,0,n){
char ch='a';
FORE(j,0,words[i].size()){
if(words[i][j]==ch)ch++;
else if(words[i][j]>ch){
char prev=words[i][j];
FORE(k,j,words[i].size()){
if(words[i][k]==ch)words[i][k]=prev;
else if(words[i][k]==prev)words[i][k]=ch;
}
ch++;
}
}
}
int ret=0;
int used[n];
memset(used,0,sizeof(used));
FORE(i,0,n)if(used[i]==0){
int cnt=0;
FORE(j,i,n)if(used[j]==0 && words[i]==words[j]){
used[j]=1,cnt++;
}
ret+=cnt*(cnt-1)/2;
}
return ret;
}
};