[Java/C++] Memoization DFS & KMP - with Picture - Clean code ~ 12ms
Some words\nIt\'s a really hard problem. For this problem I prefer to explain in the solution code. I also create a following example with explanation picture, 
**Some words**\nIt\'s a really hard problem. For this problem I prefer to explain in the solution code. I also create a following example with explanation picture, hope you can understand a bit from that.\n\n**Input:** n = 2, s1 = "db", s2 = "fe", evil = "e"\n**Output:** 24+4=28\n**Explanation:**\n![image](https://assets.leetcode.com/users/hiepit/image_1585506505.png)\n\n\n**Java ~ 12ms**\n```java\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        int[] dp = new int[1 << 17]; // Need total 17 bits, can check getKey() function\n        return dfs(0, 0, true, true,\n                n, s1.toCharArray(), s2.toCharArray(), evil.toCharArray(), computeLPS(evil.toCharArray()), dp);\n    }\n    int dfs(int i, int evilMatched, boolean leftBound, boolean rightBound,\n            int n, char[] s1, char[] s2, char[] evil, int[] lps, int[] dp) {\n        if (evilMatched == evil.length) return 0; // contain `evil` as a substring -> not good string\n        if (i == n) return 1; // it\'s a good string\n        int key = getKey(i, evilMatched, leftBound, rightBound);\n        if (dp[key] != 0) return dp[key];\n        char from = leftBound ? s1[i] : \'a\';\n        char to = rightBound ? s2[i] : \'z\';\n        int res = 0;\n        for (char c = from; c <= to; c++) {\n            int j = evilMatched; // j means the next match between current string (end at char `c`) and `evil` string\n            while (j > 0 && evil[j] != c) j = lps[j - 1];\n            if (c == evil[j]) j++;\n            res += dfs(i + 1, j, leftBound && (c == from), rightBound && (c == to),\n                    n, s1, s2, evil, lps, dp);\n            res %= 1000000007;\n        }\n        return dp[key] = res;\n    }\n    int getKey(int n, int m, boolean b1, boolean b2) {\n        // Need 9 bits store n (2^9=512), 6 bits store m (2^6=64), 1 bit store b1, 1 bit store b2\n        return (n << 8) | (m << 2) | ((b1 ? 1 : 0) << 1) | (b2 ? 1 : 0);\n    }\n    int[] computeLPS(char[] str) { // Longest Prefix also Suffix\n        int n = str.length;\n        int[] lps = new int[n];\n        for (int i = 1, j = 0; i < n; i++) {\n            while (j > 0 && str[i] != str[j]) j = lps[j - 1];\n            if (str[i] == str[j]) lps[i] = ++j;\n        }\n        return lps;\n    }\n```\n\n**C++ ~ 20ms**\n```c++\n    int dp[501][51][2][2] = {};\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        return dfs(0, 0, true, true,\n\t\t\tn, s1, s2, evil, computeLPS(evil));\n    }\n    int dfs(int i, int evilMatched, bool leftBound, bool rightBound,\n\t\t\tint n, string& s1, string& s2, string& evil, const vector<int>& lps) {\n        if (evilMatched == evil.size()) return 0; // contain `evil` as a substring -> not good string\n        if (i == n) return 1; // it\'s a good string\n        if (dp[i][evilMatched][leftBound][rightBound] != 0) return dp[i][evilMatched][leftBound][rightBound];\n        char from = leftBound ? s1[i] : \'a\';\n        char to = rightBound ? s2[i] : \'z\';\n        int res = 0;\n        for (char c = from; c <= to; c++) {\n            int j = evilMatched; // j means the next match between current string (end at char `c`) and `evil` string\n            while (j > 0 && evil[j] != c) j = lps[j - 1];\n            if (c == evil[j]) j++;\n            res += dfs(i + 1, j, leftBound && (c == from), rightBound && (c == to),\n                    n, s1, s2, evil, lps);\n            res %= 1000000007;\n        }\n        return dp[i][evilMatched][leftBound][rightBound] = res;\n    }\n    vector<int> computeLPS(const string& str) { // Longest Prefix also Suffix\n        int n = str.size();\n        vector<int> lps = vector<int>(n);\n        for (int i = 1, j = 0; i < n; i++) {\n            while (j > 0 && str[i] != str[j]) j = lps[j - 1];\n            if (str[i] == str[j]) lps[i] = ++j;\n        }\n        return lps;\n    }\n```\n\nComplexity\n- Time: `O(n*m*2*2*26)`, where `n<=500`, `m<=50` is length of `evil`\n- Space: `O(m*n*2*2)`\n\n**Reference**\n- KMP Table: [1392. Longest Happy Prefix](https://leetcode.com/problems/longest-happy-prefix/discuss/553594/java-6-lines-kmp-solution-clean-code-on)\n\nInspired by @plus2047 from this [post](https://leetcode.com/problems/find-all-good-strings/discuss/554806/)\n\nIf it helps you easy to understand, please help to **UPVOTE**.\nIf you have any questions, feel free to comment below.\nHappy coding!
[]