题解 | #查找兄弟单词#
查找兄弟单词
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;
}