# Accepted recursive solution using Trie Tree

• The idea is quite simple. Just use a trie tree to accelerate testing whether a substring is valid. The value of each TrieNode is used to deal with duplication and to mark whether the word is used before.

``````      static class TrieNode {
int value = 0;
Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
}

TrieNode trie;

// build a trie tree
public List<Integer> findSubstring(String S, String[] L) {
trie = buildTrie(L);
int length = getTotalLength(L);
for (int i = 0; i < S.length() - length + 1; i++) {
if (isSubString(S, i, i + length))
}
return result;
}

private int getTotalLength(String[] L) {
int sum = 0;
for (String l : L)
sum += l.length();
return sum;
}

private TrieNode buildTrie(String[] L) {
TrieNode root = new TrieNode();
for (String l : L)
return root;
}

private void addWord(TrieNode root, String s) {
TrieNode node = root;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
TrieNode next = node.children.get(c);
if (next == null) {
next = new TrieNode();
node.children.put(c, next);
}
node = next;
}
node.value++;
}

private boolean isSubString(String S, int start, int end) {
if (start == end)
return true;
// search in the trie tree
TrieNode node = trie;
for (int i = start; i < end; i++) {
char c = S.charAt(i);
if (node.children.get(c) == null)
return false;
node = node.children.get(c);
if (node.value > 0) {  // leaf & can be used
node.value--; // mark as used
if (isSubString(S, i + 1, end)) {
node.value++; // mark as unused
return true;
}
node.value++; // mark as unused
}
}
return false;
}``````

• Thanks for sharing! Follow your idea and write a C++ version, 76ms. `Char has its own index`, maybe array is better than hashmap,

``````class TrieNode{
public:
TrieNode* child[26];
int cnt;
TrieNode(): cnt(0){
memset(child, NULL, sizeof(TrieNode*)*26);
}
};

class Trie{
TrieNode* root;
public:
Trie(){
root = new TrieNode();
}
TrieNode* getRoot(){
return root;
}
void buildTrie(vector<string>& words){
for (string w : words) {
}
}
TrieNode* cur=root;
for(int i=0; i<word.size(); i++){
int idx=word[i]-'a';
if(cur->child[idx]==NULL){
cur->child[idx]=new TrieNode();
}
cur=cur->child[idx];
}
cur->cnt++;
}
};

class Solution {
public:
Trie* trie;
vector<int> findSubstring(string s, vector<string>& words) {
trie= new Trie();
trie->buildTrie(words);
int length = 0;
for (string w : words) {
length += w.length();
}

vector<int> result;
for (int i = 0; i < s.length() - length + 1; i++) {
if (isSubString(s, i, i + length))
result.push_back(i);
}
return result;
}
bool isSubString(string& s, int start, int end) {
TrieNode* node = trie->getRoot();
int idx;
for (int i = start; i < end; i++) {
idx = s[i]-'a';
if (node->child[idx] == NULL) return false;
node = node->child[idx];
if(node->cnt>0){
node->cnt--; // mark as used
if (i + 1==end || isSubString(s, i + 1, end)) {
node->cnt++; // mark as unused
return true;
}
node->cnt++; // mark as unused
}
}
return false;
}
};``````

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