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

题目

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

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

以空格分隔…….

思路

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

代码

    /*---------------------------------------------
 * 日期：2015-02-26
 * 作者：SJF0115
 * 题目: 字符串唯一前缀问题
 * 来源：经典面试题
 * 博客：
 -----------------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

#define MAX 26

struct 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;
        }//if
        TrieNode *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
    }//Insert
// 字符串的唯一前缀表示
string 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
        }//for
return 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;
        }//if
        TrieNode *root = new TrieNode();
// 创建字典树
for(int i = 0;i < size;++i){
            Insert(root,strs[i]);
        }//for
// 唯一前缀
for(int i = 0;i < size;++i){
            prefix.first = strs[i];
            prefix.second = OnlyPrefix(root,strs[i]);
            vec.push_back(prefix);
        }//for
return 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）