[经典面试题][字典树]字符串唯一前缀问题

题目

一个文件里面有如下字符串 cartefdxh cart carlkijfwe chdfwef cafkekfld …………

要从文件中找出唯一能代表该字符串的前缀，，然后如下输出 cartefdxh carte cart cart carlkijfwe carl chdfwef ch cafkekfld caf

以空格分隔…….

思路

用Trie树实现。为每个节点增加一个变量count，用来记录一共有几个字符串使用该字符。找节点计数为1的节点或者叶子节点。

代码

/*———————————————* 日期：2015-02-26* 作者：SJF0115* 题目: 字符串唯一前缀问题* 来源：经典面试题* 博客：———————————————–*/;#define MAX 26struct TrieNode{// 有几个字符串公用这个字符int count;TrieNode *next[MAX];TrieNode(){count = 0;for(int i = 0;i < MAX;++i){next[i] = NULL;}//for}};// 插入void Insert(TrieNode* &root,string str){int size = str.size();if(size == 0){return;}//ifTrieNode *p = root;int val;for(int i = 0;i < size;++i){val = str[i] – ‘a’;if(p->next[val] == NULL){p->next[val] = new TrieNode();}//if// 统计共有几个字符串共用该字符p->next[val]->count++;p = p->next[val];}//for}OnlyPrefix(TrieNode* root,string str){int size = str.size();TrieNode *p = root;int index = 0,val;for(int i = 0;i < size;++i){val = str[i] – ‘a’;index++;p = p->next[val];if(p->count == 1){break;}//if}//forreturn str.substr(0,index);}// 所有字符串的唯一前缀表示vector<pair<string,string> > AllOnlyPrefix(vector<string> strs){int size = strs.size();pair<string,string> prefix;vector<pair<string,string> > vec;if(size <= 0){return vec;}//ifTrieNode *root = new TrieNode();// 创建字典树for(int i = 0;i < size;++i){Insert(root,strs[i]);}(int i = 0;i < size;++i){prefix.first = strs[i];prefix.second = OnlyPrefix(root,strs[i]);vec.push_back(prefix);}//forreturn vec;}int main() {vector<string> strs = {“book”,”boom”,”cartefdxh”,”cart”,”carlkijfwe”,”chdfwef”,”cafkekfld”};vector<pair<string,string> > vec = AllOnlyPrefix(strs);for(int i = 0;i < vec.size();++i){pair<string,string> pair = vec[i];cout<<pair.first<<” “<<pair.second<<endl;}//for}

引用：

[算法系列之二十]字典树（Trie）

莫找借口失败，只找理由成功。(不为失败找理由，要为成功找方法)