Longest Word in Dictionary LeetCode solution in C++

1
struct node {
2
  int end = 0;
3
  node *adj[26];
4
};
5

6
class Solution {
7
 public:
8
  string longestWord(vector<string> &words) {
9
    auto root = new node();
10
    auto insert = [&](string &s, int ind) {
11
      node *cur = root;
12
      int i;
13
      for (char &c : s) {
14
        i = c - 'a';
15
        if (!cur->adj[i]) cur->adj[i] = new node();
16
        cur = cur->adj[i];
17
      }
18
      cur->end = ind;
19
    };
20

21
    int ind = 0;
22
    for (string &s : words) insert(s, ++ind);
23

24
    stack<node *> st;
25
    st.push(root);
26
    string ans = "";
27
    while (!st.empty()) {
28
      node *cur = st.top();
29
      st.pop();
30
      if (cur->end > 0 || cur == root) {
31
        if (cur != root) {
32
          string word = words[cur->end - 1];
33
          if (word.size() > ans.size() || (word.size() == ans.size() && word < ans)) {
34
            ans = word;
35
          }
36
        }
37

38
        for (int j = 0; j < 26; j++)
39
          if (cur->adj[j]) st.push(cur->adj[j]);
40
      }
41
    }
42
    return ans;
43
  }
44
};