头条笔试第二题，最短前缀

头条笔试第二题，最短前缀

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

const int ALPHABET_SIZE = 26;

struct TrieNode
{
    struct TrieNode* children[ALPHABET_SIZE];
    int n;
};

TrieNode* init_node()
{
    TrieNode *pNode = new TrieNode;
    pNode->n = 0;
    for (int i=0; i<ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;

    return pNode;
}

void insert(TrieNode* root, string key)
{
    TrieNode *pNode = root;

    for (int i=0; i<key.size(); i++) {
        int index = key[i] - 'a';
        if (NULL == pNode->children[index]) {
            pNode->children[index] = init_node();
        }
        pNode->n = pNode->n + 1;
        pNode = pNode->children[index];
    }
}

vector<string> shortest_prefix(vector<string>& strs)
{
    TrieNode *root = init_node();
    for (int i=0; i<strs.size(); i++)
        insert(root, strs[i]);

    int i, j, index;
    vector<string> prefix;
    TrieNode *pNode;
    for (i=0; i<strs.size(); i++) {
        pNode = root;
        for (j=0; j<strs[i].size(); j++) {
            index = strs[i][j] - 'a';
            if (pNode->children[index]->n <= 1)
                break;
            pNode = pNode->children[index];
        }
        prefix.push_back(strs[i].substr(0, j+1));
    }

    return prefix;
}

int main()
{
    vector<string> strs;
    strs.push_back("bytedance");
    strs.push_back("toutiaohao");
    strs.push_back("toutiaoapp");
    strs.push_back("iesac");
    strs.push_back("iestc");

    vector<string> ret = shortest_prefix(strs);
    for (int i=0; i<ret.size(); i++)
        cout << ret[i] << endl;

    /*
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> str;
        strs.push_back(str);
    }
    vector<string> ret = shortest_prefix(strs);
    for (int i=0; i<ret.size(); i++)
        cout << ret[i] << endl;
    */

    return 0;
}

仅供参考。