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


题目描述:
一个文件里面有如下字符串
cartefdxh
cart
carlkijfwe
chdfwef
cafkekfld
............

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

以空格分隔.......
已邀请:

sjf0115 - Stay Hungry, Stay Foolish

赞同来自:


思路:

为每个节点加一个计数,找节点计数为1的节点或者叶子节点

1.png


代码
        /*---------------------------------------------
    *   日期: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
    }


不知道代码有问题没?欢迎指正,优化.........

要回复问题请先登录注册