题目
一个单词单词字母交换，可得另一个单词，如army->mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程。
思路一
兄弟单词必须满足字符相同，相同字符个数也必须相同。基于这点用Hash实现：
（1）申请一个int数组 count[26]用来统计每个字符出现的次数。
（2）扫描字典中的单词，只考虑长度和给出单词长度一样大小的单词（长度不同肯定不是兄弟单词），用broCount[26]来统计单词中每个字符出现的次数。
（3）如果count和broCount一样，表示是兄弟单词否则不是。
代码一
/*---------------------------------------------
* 日期：2015-02-22
* 作者：SJF0115
* 题目: 兄弟单词
* 来源：百度
* 博客：
-----------------------------------------------*/
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
class Solution {
public:
// dic字典集合 word查找单词
vector<string> BrotherWord(vector<string> dic,string word){
int count[26];
vector<string> brother;
// 初始化
memset(count,0,sizeof(count));
int wordSize = word.size();
int dicSize = dic.size();
// 统计字符以及个数
for(int i = 0;i < wordSize;++i){
++count[word[i]-'a'];
}//for
// 遍历字典
for(int i = 0;i < dicSize;++i){
if(IsBrother(word,count,dic[i])){
brother.push_back(dic[i]);
}//if
}//for
return brother;
}
private:
bool IsBrother(string word,int count[],string broWord){
int size = broWord.size();
int wordSize = word.size();
// 长度不一样肯定不是兄弟单词
if(size != wordSize){
return false;
}//if
// 统计字符及个数
int broCount[26];
memset(broCount,0,sizeof(broCount));
for(int i = 0;i < size;++i){
++broCount[broWord[i]-'a'];
}//for
// 只有字符一样，字符个数一样才是兄弟单词
int k;
for(k = 0;k < 26;++k){
// 不是兄弟单词
if(count[k] != broCount[k]){
break;
}//if
}//for
if(k == 26){
return true;
}//if
return false;
}
};
int main() {
Solution solution;
vector<string> dic = {"mary","many","book","army","mood","man","doom","mod"};
string word("mary");
vector<string> result = solution.BrotherWord(dic,word);
for(int i = 0;i < result.size();++i){
cout<<result[i]<<" ";
}//for
cout<<endl;
}思路二：
在字典树的中再存储一个vector结构的容器来储存兄弟单词。
struct TrieNode{
TrieNode *next[MAX];
vector<string> brother;
TrieNode(){
for(int i = 0;i < MAX;++i){
next[i] = NULL;
}//for
}
};字典树的建立是在预处理阶段完成的，首先根据字典中的单词来建立字典树，建立的时候，需要稍微特殊处理一下，就是比如mary、army互为兄弟单词，如果先插入单词mary，首先对其进行排序，结果是amry，那么字典树中就分别建立4个节点，分别为a->m->r->y，在节点y处的vector容器brother中添加单词mary，插入army的时候，同样的原理，先排序，再插入，此时发现这4个节点已经建立了，那么只需要在第四个节点y处的vector容器brother中添加单词army。
这样建立完字典树后，查询兄弟单词的效率就会很高了，比哈希的效率还要高；查询army的兄弟单词时，先排序（amry），然后在字典树中查找amry，在y处vector容器brother中的的单词就是所有兄弟单词。
代码二
/*---------------------------------------------
* 日期：2015-02-23
* 作者：SJF0115
* 题目: 兄弟单词
* 来源：百度
* 博客：
-----------------------------------------------*/
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 26
struct TrieNode{
TrieNode *next[MAX];
vector<string> brother;
TrieNode(){
for(int i = 0;i < MAX;++i){
next[i] = NULL;
}//for
}
};
// 插入
void Insert(TrieNode* &root,string str){
int size = str.size();
TrieNode *p = root;
string tmp = str;
// 排序
sort(tmp.begin(),tmp.end());
// 插入
int val;
for(int i = 0;i < size;++i){
val = tmp[i] - 'a';
if(p->next[val] == NULL){
p->next[val] = new TrieNode();
}//if
p = p->next[val];
}//for
p->brother.push_back(str);
}
// 预处理
void Init(vector<string> dic,TrieNode* &root){
int dicSize = dic.size();
if(dicSize <= 0){
return;
}//if
// 创建字典树
for(int i = 0;i < dicSize;++i){
Insert(root,dic[i]);
}//for
}
// 打印字典
void PrintDic(TrieNode* root){
if(root == NULL){
return;
}//if
if(root->brother.size() > 0){
for(int i = 0; i < root->brother.size();++i){
cout<<root->brother[i]<<" ";
}//for
cout<<endl;
}//if
for(int i = 0;i < 26;++i){
PrintDic(root->next[i]);
}//for
}
// 兄弟单词
vector<string> BrotherWord(TrieNode *root,string word){
int size = word.size();
vector<string> brother;
if(root == NULL || size <= 0){
return brother;
}//if
// 排序
sort(word.begin(),word.end());
TrieNode *p = root;
int val;
for(int i = 0;i < size;++i){
val = word[i] - 'a';
if(p->next[val] == NULL){
return brother;
}//if
p = p->next[val];
}//for
return p->brother;
}
int main() {
vector<string> dic = {"mary","many","book","army","mood","mray","man","doom","mod"};
string word("mod");
TrieNode *root = new TrieNode();
// 预处理 创建字典树
Init(dic,root);
// 查询兄弟单词
vector<string> result = BrotherWord(root,word);
if(result.size() <= 0){
cout<<"单词["<<word<<"]没有兄弟单词"<<endl;
}//if
else{
cout<<"单词["<<word<<"]有兄弟单词:";
for(int i = 0;i < result.size();++i){
cout<<result[i]<<" ";
}//for
cout<<endl;
}
}
引用：
