[经典面试题][百度]寻找兄弟单词

题目

一个单词单词字母交换，可得另一个单词，如army->mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程。

思路一 兄弟单词必须满足字符相同，相同字符个数也必须相同。基于这点用Hash实现： （1）申请一个int数组 count[26]用来统计每个字符出现的次数。 （2）扫描字典中的单词，只考虑长度和给出单词长度一样大小的单词（长度不同肯定不是兄弟单词），用broCount[26]来统计单词中每个字符出现的次数。 （3）如果count和broCount一样，表示是兄弟单词否则不是。

代码一

/*———————————————* 日期：2015-02-22* 作者：SJF0115* 题目: 兄弟单词* 来源：百度* 博客：———————————————–*/;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’];}(int i = 0;i < dicSize;++i){if(IsBrother(word,count,dic[i])){brother.push_back(dic[i]);}//if}//forreturn brother;}private:bool IsBrother(string word,int count[],string broWord){int size = broWord.size();int wordSize = word.size();// 长度不一样肯定不是兄弟单词if(size != wordSize){return false;}broCount[26];memset(broCount,0,sizeof(broCount));for(int i = 0;i < size;++i){++broCount[broWord[i]-‘a’];}k;for(k = 0;k < 26;++k){// 不是兄弟单词if(count[k] != broCount[k]){break;}//if}//forif(k == 26){return true;};}};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]<<” “;}//forcout<<endl;}

，人生就像是一场旅行，遇到的既有感人的，