题解 | #查找兄弟单词#

二刷

二刷又有新的感悟

判断是否是兄弟串，可以这样写

// 判断s1串和s2串是否是兄弟
bool isBro(string s1, string s2) {
    if(s1.size() != s2.size()) return false;
    vector<int> hash1(26, 0);
    vector<int> hash2(26, 0);
    for(int i = 0; i < s1.size(); i++) {
        hash1[int(s1[i] - 'a')]++;
        hash2[int(s2[i] - 'a')]++;
    }
    return hash1 == hash2;
}

查找兄弟串可以这样写,思路更整体，代码也更简洁

void findBro(vector<string> s, string str, int k) {
    vector<string> brostr;
    for(int i = 0; i < s.size();i++) {
        if(isBro(s[i], str)) {
            brostr.push_back(s[i]);
        }
    }
    sort(brostr.begin(), brostr.end());
    cout << brostr[k - 1];
}

思路

这道题目有两个难点，一是如何判断两个串是兄弟串；二是当k的值大于兄弟串个数的时候，要注意判断输出

针对1，在本题中，ifBro(string s1, string s2)中的s1和s2串长度一致且不相等。因此，可以对两个串分别建立大小为26的hash表，只要两个串对应的hash表相同，那么必然是兄弟子串

针对2，只需要在main函数输出的时候，加一个if语句判断下就OK

#include <bits/stdc++.h>
using namespace std;

bool ifBro(string s1, string s2) {
    //如果是兄弟子串，那么hashtable的值必然是相同的
    vector<int> hashtable1(26,0);
    vector<int> hashtable2(26,0);
    int size = s1.size();
    bool flag = false;
    for(int i = 0; i < size; i++) {
        hashtable1[s1[i]-'a']++;
        hashtable2[s2[i]-'a']++;
    }
    if(hashtable1 == hashtable2) {
        flag = true;
    }
    return flag;
}


int judgeBro(vector<string> &str, string s) {
    int count = 0;//计数，看有几个兄弟
    vector<string> temp;
    for(int i = 0; i < str.size(); i++) {
        //str中串和s串的长短不一致 or str串和s串相同，则都不是兄弟子串
        if(str[i].size() != s.size() || str[i] == s) continue;
        else if(ifBro(str[i], s) == true){
            count++;
            temp.push_back(str[i]);
        }
    }
    sort(temp.begin(), temp.end());
    str = temp;
    return count;
}

int main()
{
    //初始化元素，并输入
    int n,k;
    string s1,s2;
    vector<string> str;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s1;
        str.push_back(s1);
    }
    cin >> s2;
    cin >> k;
    int ans = judgeBro(str, s2);
    cout << ans <<endl;

    //如果k比兄弟单词的个数多，就不能打印
    if(k > ans) {
        return 0;
    }
    cout << str[k-1];
    return 0;
}