algorithm/Week_04/id_52/LeetCode_720_052.cpp at master · algorithm003/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class Solution {
public:
    //Trie datastructure:
    static const int ALPHABET_SIZE = 26;

    // trie node
    struct TrieNode
    {
        struct TrieNode *children[ALPHABET_SIZE];

        // isEndOfWord is true if the node represents
        // end of a word
        bool isEndOfWord;
    };

    // Returns new trie node (initialized to NULLs)
    struct TrieNode *getNode(void)
    {
        struct TrieNode *pNode =  new TrieNode;

        pNode->isEndOfWord = false;

        for (int i = 0; i < ALPHABET_SIZE; i++)
            pNode->children[i] = NULL;

        return pNode;
    }

    // If not present, inserts key into trie
    // If the key is prefix of trie node, just
    // marks leaf node
    void insert(struct TrieNode *root, string key)
    {
        struct TrieNode *pCrawl = root;

        for (int i = 0; i < key.length(); i++)
        {
            int index = key[i] - 'a';
            if (!pCrawl->children[index])
                pCrawl->children[index] = getNode();

            pCrawl = pCrawl->children[index];
        }

        // mark last node as leaf
        pCrawl->isEndOfWord = true;
    }

    // Returns true if key presents in trie, else
    // false
    bool search(struct TrieNode *root, string key)
    {
        struct TrieNode *pCrawl = root;

        for (int i = 0; i < key.length(); i++)
        {
            int index = key[i] - 'a';
            if (!pCrawl->children[index])
                return false;

            pCrawl = pCrawl->children[index];
        }

        return (pCrawl != NULL && pCrawl->isEndOfWord);
    }
    ///////


    //start of the program
    string ans="";

    void dfs(struct TrieNode *root, string key){
        //process node
        if(key.length()>ans.length())
            ans= key;

        //For every child of node
        for (int i = 0; i < ALPHABET_SIZE; i++)
            if(root->children[i] != NULL && root->children[i]->isEndOfWord)
                dfs(root->children[i],key+char('a'+i)  );


    }

    string longestWord(vector<string>& words) {
        //build up a trie
        struct TrieNode *root = getNode();
        for(int i=0 ; i<words.size(); i++)
            insert(root,words[i]);

        //DFS
        dfs(root,"");
        cout<<ans<<endl;

        return ans;
    }


};