题解 | #查找兄弟单词#

查找兄弟单词

http://www.nowcoder.com/practice/03ba8aeeef73400ca7a37a5f3370fe68

用的回溯法,通过实验发现,通过实践发现回溯真的不应该轻易用。

最后通过的版本如下,如果还有优化空间希望能指点一下,谢谢🙏

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

string path;
int res = 0;
unordered_map<char, int> temp;
vector<string> ans;

void backtracking(vector<string>& str, unordered_map<char, int>& hash, int n, int len, int index) {
    if (path.size() == len) {
        if (hash == temp) {
            ans.push_back(path);
            ++res;
        }
        return;
    }
    for (int i = 0; i < str.size(); i++) {
        path = str[i];
        for (int j = 0; j < path.size(); j++) {
            temp[path[j]]++;
        }
        backtracking(str, hash, n, len, i + 1);
        path = "";
        temp.clear();
    }
}

int main() {
    int n, k, len;
    string x;
    unordered_map<char, int> hash;

    cin >> n;
    
    vector<string> str(n);
    vector<string> mStr;
    
    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }
    
    cin >> x >> k;
    len = x.size();
    
    for (int i = 0; i < len; i++) {
        hash[x[i]]++;
    }
    
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == x || str[i].size() != len) {
            continue;
        }
        mStr.push_back(str[i]);
    }
    
    backtracking(mStr, hash, n, len, 0);
    
    sort(ans.begin(), ans.end());

    if (ans.size() < 1) {
        cout << 0 << endl;
    }
    
    if (ans.size() >= 1) {
        cout << ans.size() << endl;
        cout << ans[k - 1] << endl;        
    }
    
    return 0;
}
全部评论

相关推荐

如题,字节跳动怎么才能看到自己的面评,找hr说看不到
SoulStar:自己应该看不到,这个是字节比较保密的信息,之前有mentor加我,说他能看到,但是不能给我说,给我说了他可能就要被辞退了
点赞 评论 收藏
分享
双非坐过牢:非佬,可以啊10.28笔试,11.06评估11.11,11.12两面,11.19oc➕offer
点赞 评论 收藏
分享
感性的干饭人在线蹲牛友:🐮 应该是在嘉定这边叭,禾赛大楼挺好看的
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务