Java | Trie Solution | Clear examples
Lets say,\ns="aba"\nt="aab"\n\nSubstrings of t will be,\n\n\ta      .................... answer = 1 ( \'b\' = 1 )\n\taa     .................... answer = 2 ( \'
Lets say,\ns="aba"\nt="aab"\n\nSubstrings of t will be,\n\n\ta      .................... answer = 1 ( \'b\' = 1 )\n\taa     .................... answer = 2 ( \'ba\' = 1, \'ab\' = 1 ).\n\taab    .................... answer = 0 as no eligible strings are present.\n\t a     .................... answer = 1 ( \'b\' = 1 )\n\t ab    .................... answer = 0 as no eligible strings are present.\n\t  b    .................... answer = 2 ( \'a\' = 2 )\nAnswer will be 6.\n\n**Solution:**\n\nSubstrings of s will be,\n\n\ta\n\tab\n\taba\n\t b\n\t ba\n\t  a\n\t\nLets insert them in a Trie.\n![image](https://assets.leetcode.com/users/images/d12b0ac3-b64a-49fd-82eb-1662fc6b96af_1644394712.4317794.png)\n Everytime a substring enters into a node we increment the count by 1.\n \n Now our target is to find the the counts by iterating over them.\n \n **Example:**\n \n lets say our target string is **aa**.\n Also lets consider we can take all the characters (a-z) to generate substrings.\n **then, substrings with length 1 would be:**\n a,b,c,d,.....,z\n Among them answer for substring \'a\' would be 0 as there is no difference b/w source string (a) and current string (a).\n And for \'b\' to \'z\' ans would be 1 as difference b/w source string (a) and current string (b-z) is exactly 1. But only \'b\' is present in the Trie so only \'b\' is valid.\n \n **substrings with length 2 would be:**\n \n aa, ab, ac, .... az\n &\n ba, bb, bc, ... bz\n &\n ca, cb, .. cz\n ....\n .....\n za, .. zz\n \n Among them \'aa\' is not valid.\n But we can have answer for \'ab\' or \'ba\' as they have exactly 1 difference and they are present in the tree.\n \n Seeing those examples we can go with this way:\n At each step we can either go with\n\t **1. unchanged element with given difference (default 0).**\n\t **2. changed element with increased difference. (given + 1).**\n\nNow look at the below graph:\nHere our target string is \'aa\'.\nAnd we are calculating answer for each substring that have the last element as \'a\'.\n\n\taa\n\t----\n\ta\n\taa\n\t a\n\n![image](https://assets.leetcode.com/users/images/f887d5a9-0ae4-4d0f-9d46-7b5ca01da83f_1644399882.0430264.png)\n\n\nSimilarly for \'aab\':\nsubstrings will be:\n\t\n\ta\n\taa\n\taab\n\t a\n\t ab\n\t  b\n\t\t\nHere is the code:\n\n```\nclass Solution {\n    class Trie{\n        Trie[] nodes = new Trie[26];\n        int count = 0;\n        Set<Integer> child = new HashSet<>();\n        void add(String s, int startIndex, int endIndex){\n            Trie current = this;\n            for (int i = startIndex; i<endIndex; i++){\n                if (current.nodes[getInt(s.charAt(i))]==null){\n\t\t\t\t\t// if trie node is not present at ith index, we create a new node\n\t\t\t\t\t// and the index gets added to current child set.\n\t\t\t\t\t// instead of iterating over all 26 nodes, we are iterating over the child set, to enhance performance\n                    current.nodes[getInt(s.charAt(i))] = new Trie();\n                    current.child.add(getInt(s.charAt(i)));\n                }\n                current.nodes[getInt(s.charAt(i))].count++;\n                current = current.nodes[getInt(s.charAt(i))];\n            }\n        }\n    }\n    int find(Trie t, String s, int index, int difference, String carry){\n    \tint ans = 0;\n    \tif (difference==1)\n    \t\tans+=t.count;//if current difference is 1 we increment the answer with current node\'s count\n    \tif (difference==2)\n    \t\treturn ans;\n    \tif (index>s.length()-1) {\n    \t\treturn ans;\n    \t}\n    \tif (t==null)\n    \t\treturn 0;\n\t\t//without changing the current element and keeping the given difference\n    \tif (t.nodes[getInt(s.charAt(index))]!=null) {\n    \t\tans+=find(t.nodes[getInt(s.charAt(index))], s, index+1, difference, carry+s.charAt(index));\n    \t}\n\t\t//changing the current element and incrementing difference by 1\n    \tfor (int inx: t.child) {\n    \t\tif (inx!=getInt(s.charAt(index))) { //only proceed when it is a different element\n    \t\t\tans+=find(t.nodes[inx], s, index+1, difference+1, carry+(char)(inx+\'a\'));\n    \t\t}\n    \t}\n    \treturn ans;\n    }\n    int getInt(char c){\n        return c-\'a\';\n    }\n    public int countSubstrings(String s, String t) {\n        Trie trie = new Trie();\n        for (int i = 0; i<s.length(); i++){\n            trie.add(s, i, s.length()); // generating the Trie\n        }\n        int ans = 0;\n        for (int i = 0; i<t.length(); i++) {\n        \tans+=find(trie, t, i, 0, ""); // getting the answer for substrings i to n\n        }\n        return ans;\n    }\n}\n```\n\nTime Complexity:\nCorrect me if I am wrong.\ns_len = sizeof(s);\nt_len = sizeof(t);\n\ns_len * s_len + t_len * k^(t_len)\nwhere k can be between 1 to 26\n\n
['Depth-First Search', 'Trie', 'Java']