[经典面试题][字典树]字符串唯一前缀问题 |
您所在的位置：网站首页 › 前缀树是什么 › [经典面试题][字典树]字符串唯一前缀问题 |
[经典面试题][字典树]字符串唯一前缀问题
|
题目 一个文件里面有如下字符串 cartefdxh cart carlkijfwe chdfwef cafkekfld ………… 要从文件中找出唯一能代表该字符串的前缀，然后如下输出 cartefdxh carte cart cart carlkijfwe carl chdfwef ch cafkekfld caf 以空格分隔……. 思路 用Trie树实现。为每个节点增加一个变量count，用来记录一共有几个字符串使用该字符。找节点计数为1的节点或者叶子节点。
代码 /*--------------------------------------------- * 日期：2015-02-26 * 作者：SJF0115 * 题目: 字符串唯一前缀问题 * 来源：经典面试题 * 博客： -----------------------------------------------*/ #include #include using namespace std; #define MAX 26 struct TrieNode{ // 有几个字符串公用这个字符 int count; TrieNode *next[MAX]; TrieNode(){ count = 0; for(int i = 0;i 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 next[val]; if(p->count == 1){ break; }//if }//for return str.substr(0,index); } // 所有字符串的唯一前缀表示 vector > AllOnlyPrefix(vector strs){ int size = strs.size(); pair prefix; vector > vec; if(size strs = {"book","boom","cartefdxh","cart","carlkijfwe","chdfwef","cafkekfld"}; vector > vec = AllOnlyPrefix(strs); for(int i = 0;i pair = vec[i]; cout引用： [算法系列之二十]字典树（Trie） |
【本文地址】