Rust Trie
Fix size try node for the 26 letters of the alphabet. All suffixes of s are inserted into the Trie. We also keep track in the TrieNode\nof the amount of times e
Fix size try node for the 26 letters of the alphabet. All suffixes of `s` are inserted into the Trie. We also keep track in the TrieNode\nof the amount of times each node can be reached. \n\nI decided to generalize the count method, so you technically could use this solution to track a substring difference of any size.\n\n```\n#[derive(Debug)]\nstruct Trie {\n    children: [Option<Box<Trie>>; 26],\n    count: usize,\n}\n\nimpl Trie {\n    fn new() -> Self {\n        Self {\n            children: Default::default(),\n            count: 0,\n        }\n    }\n    fn insert(&mut self, word: &[u8], index: usize) {\n        self.count += 1;\n        if word.len() == index {\n            return;\n        }\n        let v = (word[index] - b\'a\') as usize;\n        if self.children[v].is_none() {\n            self.children[v] = Some(Box::new(Self::new()));\n        }\n        self.children[v].as_mut().unwrap().insert(word, index+1);\n    }\n    fn count_one_diff(&self, word: &[u8], index: usize, allowed: usize, answer: &mut i32) {\n        if word.len() == index {\n            return;\n        }\n        let v = (word[index] - b\'a\') as usize;\n        if self.children[v].is_some() {\n            let child_ref = self.children[v].as_ref().unwrap();\n            if allowed == 0 {\n                *answer += child_ref.count as i32;\n            }\n            child_ref.count_one_diff(word, index+1, allowed, answer);\n        }\n        if allowed > 0 {\n            for i in 0..self.children.len() {\n                if v != i && self.children[i].is_some() {\n                    let child_ref = self.children[i].as_ref().unwrap();\n                    if allowed == 1 {\n                        *answer += child_ref.count as i32;\n                    }\n                    child_ref.count_one_diff(word, index+1, allowed-1, answer);\n                }\n            }\n        }\n    }\n}\n\nimpl Solution {\n    pub fn count_substrings(s: String, t: String) -> i32 {\n        let mut root = Trie::new();\n        for i in 0..s.len() {\n            root.insert(&s.as_bytes()[i..], 0);\n        }\n        root.count = 0; // This is unnecessary...\n        let mut answer = 0;\n        for i in 0..t.len() {\n            root.count_one_diff(&t.as_bytes()[i..], 0, 1, &mut answer);\n        }\n        \n        answer\n    }\n}\n```
['Rust']