题目
一个单词单词字母交换,可得另一个单词,如army->mary,成为兄弟单词。提供一个单词,在字典中找到它的兄弟。描述数据结构和查询过程。
思路一
兄弟单词必须满足字符相同,相同字符个数也必须相同。基于这点用Hash实现:
(1)申请一个int数组 count[26]用来统计每个字符出现的次数。
(2)扫描字典中的单词,只考虑长度和给出单词长度一样大小的单词(长度不同肯定不是兄弟单词),用broCount[26]来统计单词中每个字符出现的次数。
(3)如果count和broCount一样,表示是兄弟单词否则不是。
代码一
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
class Solution {
public:
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(int i = 0;i < dicSize;++i){
if(IsBrother(word,count,dic[i])){
brother.push_back(dic[i]);
}
}
return brother;
}
private:
bool IsBrother(string word,int count[],string broWord){
int size = broWord.size();
int wordSize = word.size();
if(size != wordSize){
return false;
}
int broCount[26];
memset(broCount,0,sizeof(broCount));
for(int i = 0;i < size;++i){
++broCount[broWord[i]-'a'];
}
int k;
for(k = 0;k < 26;++k){
if(count[k] != broCount[k]){
break;
}
}
if(k == 26){
return true;
}
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]<<" ";
}
cout<<endl;
}
思路二:
在字典树的中再存储一个vector结构的容器来储存兄弟单词。
struct TrieNode{
TrieNode *next[MAX];
vector<string> brother;
TrieNode(){
for(int i = 0;i < MAX;++i){
next[i] = NULL;
}
}
};
字典树的建立是在预处理阶段完成的,首先根据字典中的单词来建立字典树,建立的时候,需要稍微特殊处理一下,就是比如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中的的单词就是所有兄弟单词。
代码二
#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;
}
}
};
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();
}
p = p->next[val];
}
p->brother.push_back(str);
}
void Init(vector<string> dic,TrieNode* &root){
int dicSize = dic.size();
if(dicSize <= 0){
return;
}
for(int i = 0;i < dicSize;++i){
Insert(root,dic[i]);
}
}
void PrintDic(TrieNode* root){
if(root == NULL){
return;
}
if(root->brother.size() > 0){
for(int i = 0; i < root->brother.size();++i){
cout<<root->brother[i]<<" ";
}
cout<<endl;
}
for(int i = 0;i < 26;++i){
PrintDic(root->next[i]);
}
}
vector<string> BrotherWord(TrieNode *root,string word){
int size = word.size();
vector<string> brother;
if(root == NULL || size <= 0){
return brother;
}
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;
}
p = p->next[val];
}
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;
}
else{
cout<<"单词["<<word<<"]有兄弟单词:";
for(int i = 0;i < result.size();++i){
cout<<result[i]<<" ";
}
cout<<endl;
}
}
引用:
如何找出字典中的兄弟单词
[算法系列之二十]字典树(Trie)
寻找兄弟单词(2012.5.6百度实习)
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题
10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附...
Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 ...
C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题
阿里面试20题 百度面试10题 华为面试10题 京东面试13题 腾讯面试37题 头条面试10题 项目经理面试常遇问题 经典面试题 程序员 IT经理 项目经理 面试题 研发经理 高级程序员 经典面试题
PHP经典面试题 PHP经典面试题 PHP经典面试题 PHP经典面试题 PHP经典面试题
SQL经典面试题及答案 SQL经典面试题及答案
C语言经典面试题 对求职者很有帮助 请大家下载 免积分 攒人品
面试时整理的资料,大家可以看看,面试的java题目,面试时整理的资料,大家可以看看,面试的java题目
vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典...
2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022...
java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)
2020 java经典面试题总汇.zip
cobol面试题 cobol面试题 cobol面试题
各公司经典面试题选取
Spring经典面试题Spring经典面试题Spring经典面试题Spring经典面试题
c语音经典面试题,来自培训机构内部面试题库。
sqlserver 经典面试题。详细说明面试重点,值得参考
IT行业经典面试题,121套面试题 IT行业经典面试题,121套面试题 IT行业经典面试题,121套面试题 IT行业经典面试题,121套面试题
50+Vue经典面试题详解,你值得收藏.50+Vue经典面试题详解,你值得收藏.50+Vue经典面试题详解,你值得收藏.50+Vue经典面试题详解,你值得收藏.50+Vue经典面试题详解,你值得收藏.50+Vue经典面试题详解,你值得收藏.50...