首页 > 笔试面试题, 算法 数据结构 > 兄弟单词 — 两种算法实现

兄弟单词 — 两种算法实现

2013年2月28日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

兄弟单词这个题目最初见于《编程珠玑》,但是里面给出的方法是最笨的,一般不提倡采用吧;这个题目在之前的百度面试中也遇到过,本文实现两种方法的代码,方法如下:

方案一:使用数据结构 map<key,list>。兄弟单词共用一个签名key,key为单词内部排序后的词条,list存储同一key的单词集合;相对于编程珠玑中的方法,该方法在空间上节省了每个单词一个key的空间;在时间上,不再需要二分查找,O(1)的查找;但是这种方法还可以优化,见方案二

方案二:使用trie树。trie树又称字典树,在面试题中关于“字符串”与“数字串”类型的问题中高频出现,非常实用。对于兄弟单词,兄弟单词公用一个key自不必说,只是trie的节点结构应该多出一个域list,用来存储key对应的兄弟单词;具体节点结构应该为


bool isStr, Node* next[26], vector<const char*> brothers

该方案查询的复杂度为O(L),L为key的平均长度;空间上则有很大的优化,例如单词的key有“abc”、“abcd”、“abcde”之类的形式,则这些key也能达到空间公用,不过数据量大还好,数据量小,trie树开辟的空间还是有些浪费的,不多言,上代码:

【测试用例】


input:

cba acb bc cb b

output:

cba acb

bc cb

b

【方案一:使用哈希map实现兄弟单词】

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define MAXLEN 100  /* 单词最大长度 */

/* qsort比较函数 */
int charcmp(const void *p, const void *q)
{
	return *(char *)p - *(char *)q;
}

/* 打印输出 & 释放内存 */
void output(map<string,vector<char*>> dic)
{
	for(map<string,vector<char*>>::iterator it = dic.begin(); it != dic.end(); ++it)
	{
		for(vector<char *>::iterator itv = it->second.begin(); itv != it->second.end(); ++itv)
		{
			printf("%s ",*itv);
			free(*itv);
		}
		printf("\n");
	}
}

void main()
{
	map<string,vector<char*>> dic;  /* 存储<key,兄弟单词集> */
	char word[MAXLEN];
	int len = 0;

	while(scanf("%s",word) != EOF) /* ctrl+z结束输入 */
	{
		len = strlen(word);
		if(len > 0)
		{
			char * ptr = (char *) malloc(len+1);
			strcpy(ptr,word);
			qsort(word,len,sizeof(char),charcmp);
			string key(word);
			dic[key].push_back(ptr);
		}
	}
	output(dic);
}

【方案二:使用trie树实现兄弟单词】

注:分两个文件:BroTrie.h,定义存储兄弟单词的trie树结构;BroTrie.cpp,算法实现


/******* BroTrie.h *******/
#include <vector>

#define BRANCHNUM 26

/* trie节点 */
struct TrieNode
{
	bool isStr;  // 标记是否构成串
	TrieNode * next[BRANCHNUM];
	vector<const char*> bros;  // 存储兄弟单词集
	TrieNode():isStr(false)
	{
		memset(next,NULL,sizeof(next));
	}
};

/* trie类 */
class BroTrie
{
public:
	TrieNode * root;

	BroTrie(){ root = new TrieNode(); }

	/* 插入key对应的单词 */
	void insert(const char *key, const char *word)
	{     //check NULL....
		TrieNode * location = root;
		while(*key)
		{
			if(location->next[*key-'a'] == NULL)
			{
				TrieNode * tmp = new TrieNode();
				location->next[*key-'a'] = tmp;
			}
			location = location->next[*key-'a'];
			++key;
		}
		location->isStr = true;
		location->bros.push_back(word);
	}

	/* 输出兄弟单词 & 释放内存 */
	void outputBros(TrieNode * location)
	{     // check NULL
		if(location->isStr == true)  // 是key串,则输出该key对应的兄弟单词集
		{
			for(vector<const char*>::iterator iter = location->bros.begin();
				iter != location->bros.end(); ++iter)
			{
				printf("%s ", *iter);
			}
			printf("\n");
		}

		for(int i = 0; i < BRANCHNUM; ++i) // 释放内存
		{
			if(location->next[i] != NULL)
			{
				outputBros(location->next[i]);
			}
		}
		delete location;
	}
};
/******* BroTrie.cpp *******/
#include <iostream>
using namespace std;

#include "BroTrie.h"

#define MAXLEN 100  /* 单词最大长度 */

/* qsort比较函数 */
int charcmp(const void *p, const void *q)
{
	return *(char *)p - *(char *)q;
}

void main()
{
	BroTrie broWords;
	char word[MAXLEN];
	int len = 0;

	while(scanf("%s",word) != EOF) /* ctrl+z结束输入 */
	{
		len = strlen(word);
		if(len > 0)
		{
			char * ptr = (char *) malloc(len+1);
			strcpy(ptr,word);
			qsort(word,len,sizeof(char),charcmp);
			broWords.insert(word,ptr);
		}
	}
	broWords.outputBros(broWords.root);
}

(全文完)

  • lmmandwxy

    话说怎么老感觉算法题目不会做呢?没思路呢》

  • lmmandwxy

    学习,,,