aboutsummaryrefslogtreecommitdiff
path: root/concatenated_words.cpp
blob: 9263d8793cd5e26fa010d90f53d60183e39ff30f (plain)
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
// 472. Concatenated Words
#include "leetcode.h"

/*
 * given an array of strings 'words' (without duplicates), return all the
 * concatenated words in the given list of 'words'. a concatenated word is
 * defined as as string that is comprised entirely of at least two shorter
 * words in the given array.
 */

class Solution {
private:
  struct Trie {
    struct Trie *arr[26];
    bool end = false;
    Trie() {
      memset(arr, 0, sizeof(arr));
      end = false;
    }
  };
  Trie *root;
  void insert(string s) {
    Trie *node = root;
    for (int i = s.length() - 1; i >= 0; i--) {
      char c = s[i];
      if (!node->arr[c - 'a'])
        node->arr[c - 'a'] = new Trie();
      node = node->arr[c - 'a'];
    }
    node->end = true;
  }

public:
  vector<string> findAllConcatenatedWordsInADict(vector<string> &words) {
    sort(words.begin(), words.end(),
         [](string &w1, string &w2) { return (w1.length() <= w2.length()); });
    vector<string> ans;
    root = new Trie();
    for (string w : words) {
      if (w.length() == 0)
        continue;
      vector<bool> dp(w.length() + 1, false);
      dp[0] = true;
      for (int i = 0; i < w.length(); i++) {
        Trie *node = root;
        for (int j = i; j >= 0; j--) {
          if (node->arr[w[j] - 'a'] == NULL)
            break;
          node = node->arr[w[j] - 'a'];
          if (dp[j] && node->end) {
            dp[i + 1] = true;
            break;
          }
        }
      }
      if (dp[w.length()])
        ans.push_back(w);
      insert(w);
    }
    return ans;
  }
};

int main() {
  Solution obj;
  vector<string> words1 = {"cat", "cats",        "catsdogcats",
                           "dog", "dogcatsdog",  "hippopotamuses",
                           "rat", "ratcatdogcat"};
  vector<string> words2 = {"cat", "dog", "catdog"};
  for (auto i : obj.findAllConcatenatedWordsInADict(words1))
    cout << i << ' ';
  cout << endl;
  for (auto i : obj.findAllConcatenatedWordsInADict(words2))
    cout << i << ' ';
}