Trie

Distinct Substrings

A naive trie solution

struct Trie{
    char c;
    vector<Trie*> children;
    Trie(char c): c(c) {
        children.assign(26, nullptr);
    }
};
int solve(string s) {
    if (s.empty())return 0;
    const int n = s.length();
    Trie* root = new Trie('#');
    Trie* curr = root;
    int ret = 0;
    for (int i = 0; i < n; ++i){
        curr = root;
        for (int j = i; j < n; ++j){
            Trie* child = curr -> children[s[j] - 'a'];
            if (child == nullptr){
                ret++;
                Trie* newTrie = new Trie(s[j]);
                curr -> children[s[j] - 'a'] = newTrie;
            }
            curr = curr -> children[s[j] - 'a']; 
        }
    }
    return ret;
}

For this specified problem, we don’t need to record the character for each Trie node as the children’s index can already tell us the character information.

struct Trie{
    vector<Trie*> children;
    Trie(){
        children.assign(26, nullptr);
    }
};
int solve(string s) {
    if (s.empty())return 0;
    const int n = s.length();
    Trie* root = new Trie();
    Trie* curr = root;
    int ret = 0;
    for (int i = 0; i < n; ++i){
        curr = root;
        for (int j = i; j < n; ++j){
            Trie* child = curr -> children[s[j] - 'a'];
            if (child == nullptr){
                ret++;
                Trie* newTrie = new Trie();
                curr -> children[s[j] - 'a'] = newTrie;
            }
            curr = curr -> children[s[j] - 'a']; 
        }
    }
    return ret;
}