# C++ Simple Solution, Trie, DP

``````class Solution {
class TreeNode {
public:
public:
char c;
string word;
vector<TreeNode*> next;
TreeNode(char c) : c(c), word("") {
next.resize(26, NULL);
}
~TreeNode() {
for (TreeNode* node : next)
delete node;
}
};

bool search(TreeNode* root, string word, int l, int r) {
int n = word.size();
for (int i = l; i < r; i++) {
char c = word[i];
if (!root->next[c - 'a'])
return false;
root = root->next[c - 'a'];
}
return root->word != word && root->word != "";
}
public:
cout << 1 << endl;
vector<string> res;
TreeNode* root = new TreeNode('A'), *cur;
for (auto word : words) {
cur = root;
for (auto c : word) {
if (!cur->next[c - 'a'])
cur->next[c- 'a'] = new TreeNode(c);
cur = cur->next[c - 'a'];
}
cur->word = word;
}
for (auto word : words) {
// dp this word
int n = word.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
if (dp[j]) {
bool f = search(root, word, j, i + 1);
if (f) {
dp[i + 1] = true;
break;
}
}
}
}
if (n > 0 && dp[n])
res.push_back(word);
}
delete root;
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.