[Java] Easy to understand recursive solution without KMP
Thinking process\n\nLet me try to describe my thinking process:\n\nI\'ve decided to split the entire task into two parts: \n Calculate the whole number of strin
# Thinking process\n\nLet me try to describe my thinking process:\n\nI\'ve decided to split the entire task into two parts: \n* Calculate the whole number of strings between `s1` and `s2`;\n* How many strings contain the `evil` word.\n\n## Total number of strings\n\nLet\'s first think about the whole number of strings, which is also an interesting task, obviously you can\'t enumerate all the possible strings as there could be as much as `26^500` strings in total. What helped me with this task was to think about strings as numbers, e.g. we need to count how much numbers there are between `123` and `942` and you can neither substract them nor count iterate over all numbers.\n\nThis task splits into three easier tasks, which are:\n1) `[123..200)`.\n2) `[200..900)`.\n3) `[900..942]`.\n\nAnd they are converted to:\n1) `[23..99]`.\n2) `(9-2) * [0..99]`.\n3) `[0..42]`.\n\nWhich implies that the task could be solved recursively with additional memoization, so we want recalculate same things again.\n\nIf we convert if back to strings and chars, we could say that there are just four possible boundaries:\n`s1`, `s2`, `aa...aa` aka `A`, `zz...zz` aka `Z`. Then we have three cases from above:\n1) `s1` - `Z`.\n2) `A` - `Z`.\n3) `A` - `s2`.\n\nSo, on each step `i` we take iterate from `s1.charAt(i)` to `s2.charAt(i)` and calculate recursively case 1 for first, and case 3 for last. For all intermediate case 2 is applied:\n\n```java\nint total(int n, String s1, String s2) {\n    if (n == 0) {\n\t\treturn 1;\n\t}\n\tint total = 0;\n\tint i = s1.length() - n; \n\tfor (char s = s1.charAt(i); s <= s2.charAt(i); s++) {\n\t\tString left = s == s1.charAt(i) ? s1 : A; // left == s1 for case 1\n\t\tString right = s == s1.charAt(i) ? s2 : Z; // right == s2 for case 3\n\t\ttotal += total(n - 1, left, right);\n\t}\n\treturn total;\n}\n```\n\nMemoization was based on the next three keys: left bound, right bound and step. There are `4` bounds in total and `n` steps, so it could be an array `new int[4][4][n+1]`.\n\n## Strings with evil part\n\nAfter I was sure I have a solution which calculates all strings between `s1` and `s2` I got to the second part. My first idea was simple and it almost worked, until it met test case #43. \n\nAs our solution is recursive, we can think about bad string as the string which is prefixed with `evil` word. We should not count any string which starts with `evil`. I achieved it with an additional pointer for evil word, and if we reached the end of `evil` word - it means the string is prefixed with it and we should return `0` for its total count.\n\nLet\'s consider `s1=aaa; s2=azz; evil=ab;`. We go one by one `a..z`:\n* `a`: `a == evil.charAt(0)` => \n\t* `a`: `a != evil.charAt(1)`, so we check if `a == evil.charAt(0)` as potential new prefix, it is, so we set evil pointer to `1` again =>\n\t\t* `a`: `a != evil.charAt(1)`, so we add `1` to total;\n\t\t* `b`: `b == evil.charAt(1)`, we\'ve reached the end of `evil` string and we don\'t count it.\n\t\t* `c-z` of cource can\'t be `b`, so we add `1` for each;\n\t\t* So it\'s total `25` for `aa*`.\n\t* `b`: `b == evil.charAt(1)`, we\'ve reached the end of `evil` again and we don\'t count it all, `0` for `ab*`.\n\t* `[c-z] != evil.charAt(1)`, so we drop the pointer to `0` as neither of them are `evil.charAt(0)`, and each has `26`.\n\nSo it\'s`24 * 26 (a[c-z]*)+ 25(aa*) = 649` and below is an implementation: \n\n```java\n// DISCLAIMER: IT DOESN\'T WORK\nint total(int n, String s1, String s2, String evil, int evilPointer) {\n\tif (evilPointer == evil.length()) {\n\t\treturn 0;\n\t}\n    if (n == 0) {\n\t\treturn 1;\n\t}\n\tint total = 0;\n\tint i = s1.length() - n; \n\tfor (char s = s1.charAt(i); s <= s2.charAt(i); s++) {\n\t\tString left = s == s1.charAt(i) ? s1 : A; // left == s1 for case 1\n\t\tString right = s == s1.charAt(i) ? s2 : Z; // right == s2 for case 3\n\t\tint newEvilPointer = s == evil.charAt(evilPointer) //  if we see current character continues  continues the prefix, we move pointer \n\t\t\t\t\t\t? evilPointer + 1 \n\t\t\t\t\t\t: s == evil.charAt(0) // we have to reset pointer, when character doesn\'t continue the prefix, but if characted is the first letter of evil word, it is a potential prefix itself, so we set the pointer to 1, otherwise just drop to 0\n\t\t\t\t\t\t? 1\n\t\t\t\t\t\t: 0;\n\t\t\n\t\ttotal += total(n - 1, left, right, evil);\n\t}\n\treturn total;\n}\n```\n\n### Test Case 43 and further improvement\n\nOn the test case 43 I\'ve received the **Wrong answer** and was trying to fix modulo, as that was what I expected to be blamed. But even with `BigInteger` approach I\'ve still experienced the problem, so the modulo was fine, there was another mistake in the code. I\'ve reproduced it with own test case, which I used then to fix the problem:\n\n```\ns = "aaab"\nevil = "aab"\n```\n\nWhen we go step by step using the previous approach, we will see next:\nIt goes well till the very end of the `evil` string, then instead of the last `b` we have `a` in `s`. We pick it up as the possible beginning of `evil`, but we never reach the end of `evil` in this case, therefore we think that `s` does not contain `evil` as a substring.\n\nSo I\'ve decided to keep a list of possible `evil` begginings instead of a single pointer, as you can see in the final solution. If current character continues any of possible pointers, we increase that pointer by `1` and pass to the next recursive call, also check if the current characted is the beginning of `evil`. When any of the evil candidates reaches the end of evil string, we can say that we found it to be a prefix of our word, therefore exclude it from the total count. I used `evilCandidates.get(0)`, as the first pointer is always the largest.\n\nAnd just one more change is cache - we can encounter the same combination of left boundary, right boundary and step, but with a different evil pointer candidates, which affect the result, so we should cache the result by it. I\'ve made the cache entry to be a map, so we can use string representation of list as a key and cached result as a value. Why it matters:\n\n`s1=aa;s2=zz;evil=ab;`\n\n`a` -> `evilPointer=1` -> recursive call to `[a..z]` returns `25` because `b` makes the string have `evil` prefix. If we would cache only by `memo[A][Z][2]=25`, then we will return `25` for `b, c, ..., z`. And that is wrong, as `evilPointer=0` for all of them, therefore it should be `26`.\n# Final solution\n\n```java\nclass Solution {\n    static final int MOD = 1_000_000_000 + 7;\n    Map<String, Integer> index = new HashMap<>();\n    HashMap[][][] memo;\n    String A;\n    String Z;\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        A = generate(n, \'a\');\n        Z = generate(n, \'z\');\n\n        memo = new HashMap[4][4][n + 1];\n        index.put(s1, 0);\n        index.put(s2, 1);\n        index.put(A, 2);\n        index.put(Z, 3);\n        return f(n, s1, s2, evil, Collections.emptyList());\n    }\n    \n    private int f(int n, String s1, String s2, String evil, List<Integer> evilCandidates) {\n\t    // prefixed with evil\n        if (!evilCandidates.isEmpty() && evilCandidates.get(0) == evil.length()) {\n            return 0;\n        }\n\t\t// empty string\n        if (n == 0) {\n            return 1;\n        }\n        \n        HashMap map = memo[index.get(s1)][index.get(s2)][n];\n        \n        String key = evilCandidates.toString();\n        if (map != null && map.containsKey(key)) {\n            return (int) map.get(key);\n        }\n        int k = s1.length() - n;\n        long total = 0;\n        char c1 = s1.charAt(k), c2 = s2.charAt(k);\n        for (char s = c1; s <= c2; s++) {\n\t\t    // if we have abc to xyz, we split it into abc-azz, baa-bzz, caa-czz, ..., waa-wzz, xaa-xyz\n            String left = s == c1 ? s1 : A;\n            String right = s == c2 ? s2 : Z;\n            \n            List<Integer> nextEvil = new ArrayList<>();\n\t\t\t// if current symbol is potentially the next symbol of any candidate - add it to the new candidates list\n            for (int c : evilCandidates) {\n                if (s == evil.charAt(c)) {\n                    nextEvil.add(c + 1);\n                }\n            }\n\t\t\t// check if current character is a start of evil word\n            if (s == evil.charAt(0)) {\n                nextEvil.add(1);\n            }\n            total += f(n - 1, left, right, evil, nextEvil);\n        }\n        \n        int res = (int) (total % MOD);\n        \n        if (map == null) {\n            map = new HashMap<>();\n            memo[index.get(s1)][index.get(s2)][n] = map;\n        }\n        map.put(key, res);\n        return res;\n    }\n    \n    static String generate(int count, char c) {\n        StringBuilder sb = new StringBuilder();\n        for (int i = 0; i < count; i++) {\n            sb.append(c);\n        }\n        return sb.toString();\n    }\n}\n```
['Java']