小U的相似字符串 | 模拟

问题描述

小U认为两个字符串相似,当且仅当它们每个字母的个数都相等。例如,“abcbd"和“dbcba”是相似的,"abcd"和“abcd"也是相似的;而“abb"和“aab"不相似,“ac"和"cca”也不相似。

现在小U手中有n个字符串,她想知道有多少对字符串是相似的。

测试样例

样例1:

输入:n=7,strings=["abcbd","dbcba","abcd","abcd","adbc","aa","aa"]
输出:5

样例2:

输入:n=3,strings=["aab","bba","baa"]
输出:1

样例3:

输入:n=5,strings=["abc","def","ghi","jkl","mno"]
输出:0

题解：

        第一步：统计每个相似字符串的个数，比如在样例1中，“abcde”相似的字符串有2个，“abcd”相似的有3个，“aa”相似的有2个。

        第二步：当相似字符串的个数>=2的时候，就需要统计他的排列了，使用组合数的计算方法即可。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;

bool cmp(char x,char y){
    return x<y;
}

int C(int n,int m){
    int i,ans=1;
    for(i=n;i>n-m;i--){
        ans*=i;
    }
    for(i=1;i<=m;i++){
        ans/=i;
    }
    return ans;
}

int solution(int n, vector<string> strings) {
    // write code here
    //set<string> st;
    //cout << C(5,2) << "\n" ;
    map<string,int>mp;
    map<string,int>::iterator it;
    int i,ans=0;
    for(i=0;i<n;i++){
        sort(strings[i].begin(),strings[i].end(),cmp);
        //cout << strings[i] << "\n";
        //st.insert(strings[i]);
        mp[strings[i]]++;
    }
    //cout << mp.size() << "\n";
    for(it=mp.begin();it!=mp.end();it++){
        if(it->second>=2){
            ans+=C(it->second,2);
        }
    }
    //cout << ans << "\n";
    return ans;
}

int main() {
    cout << (solution(7, {"abcbd", "dbcba", "abcd", "abcd", "adbc", "aa", "aa"}) == 5) << endl;
    cout << (solution(3, {"aab", "bba", "baa"}) == 1) << endl;
    cout << (solution(5, {"abc", "def", "ghi", "jkl", "mno"}) == 0) << endl;
    return 0;
}