题解 | #查找兄弟单词#
查找兄弟单词
http://www.nowcoder.com/practice/03ba8aeeef73400ca7a37a5f3370fe68
思路
优先排除掉同目标字符串相同和长度不一致的字符串。剩下长度相同的,统计一下字符串各个字符出现的评率,在通过遍历 target 去删除频率,如果最终的字符映射为空,说明相同。则说明可由目标字符串变换而来。
代码
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<string> strs(n);
for( int i = 0; i < n; i++ )
cin >> strs[i];
string target;
cin >> target;
int index;
cin >> index;
int count = 0;
vector<string> res;
for( int i = 0; i < n; i++ )
{
if( strs[i].size() != target.size() || strs[i].compare(target) == 0)
continue;
unordered_map<char, int> mapping;
int len = strs[i].size();
for( int j = 0; j < len; j++ )
{
char ch = strs[i][j];
if( mapping.find(ch) != mapping.end() )
mapping[ch]++;
else
mapping[ch] = 1;
}
for( int j = 0; j < len; j++)
{
if( mapping.find(target[j]) != mapping.end() )
mapping[target[j]]--;
if(mapping[target[j]] == 0)
mapping.erase(target[j]);
}
if( mapping.empty() )
{
count++;
res.push_back(strs[i]);
}
}
cout << count << endl;
if( !res.empty() && index <= res.size() )
{
sort(res.begin(), res.end());
cout << res[index-1] << endl;
}
return 0;
}