🔥 Clean Javascript Solution - DFS
\nconst mod = 10 ** 9 + 7\n\nlet cache = null\n\n/**\n * @param {number} n\n * @param {string} s1\n * @param {string} s2\n * @param {string} evil\n * @return {n
```\nconst mod = 10 ** 9 + 7\n\nlet cache = null\n\n/**\n * @param {number} n\n * @param {string} s1\n * @param {string} s2\n * @param {string} evil\n * @return {number}\n */\nvar findGoodStrings = function(n, s1, s2, evil) {\n    /**\n     * 17 bits\n     * - 9 bit: 2 ** 9 > 500 by evil\n     * - 6 bit: 2 ** 6 > 50 by evil\n     * - 1 bit left (bound)\n     * - 1 bit right (bound)\n     *\n     * cache: `mainTraver` is the prefix length, `evilMatch` is matching for evil\n     *\n     * answer: marnTravel 0, evil 0, s prefix has the last character\n     */\n    cache = new Array(1 << 17).fill(-1)\n    return dfs(0, 0, n, s1, s2, evil, true, true, computeNext(evil))\n}\n/**\n * DFS:\n * 1. loop from `s1` to `s2`, range of position `i` is [0, n]: 0 means no start, n means complete\n * 2. if `s1` has traversed to nth, it means has been generated a legal character, and return 1; else\n * 3. `mainTravel` is the length of the `s` generated by dfs last time\n * 4. `evilMatch` is the length that matches the last generated `s` in evilMatch evil\n * 5. n, s1, s2, evil, left, right, next\n */\nfunction dfs(mainTravel, evilMatch, n, s1, s2, evil, left, right, next, ans = 0) {\n    // same length means that the match has been successful\n    if(evilMatch === evil.length) {\n        return 0\n    }\n    // this means s is conformed\n    if(mainTravel === n) {\n        return 1\n    }\n    \n    // get key for cache\n    let key = generateKey(mainTravel, evilMatch, left, right)\n    // because any combination of the four categories will only appear once, there will be no repetition\n    if(cache[key] !== -1) {\n        return cache[key]\n    }\n    \n    // get start, end calculate\n    let [start, end] = [left ? s1.charCodeAt(mainTravel) : 97, right ? s2.charCodeAt(mainTravel) : 122]\n    \n    // loop\n    for(let i = start; i <= end; i++) {\n        // get char code\n        let code = String.fromCharCode(i)\n        // actually, `evilMatch` will only get longer or stay the same, not shorter\n        let m = evilMatch\n        \n        while((m > 0) && (evil[m] !== code)) {\n            m = next[m - 1]\n        }\n\n        if(evil[m] === code) {\n            m++\n        }\n\n        // recursive\n        ans += dfs(mainTravel + 1, m, n, s1, s2, evil, left && (i === start), right && (i === end), next)\n        \n        // too large\n        ans %= mod\n    }\n\n    // result after cache set\n    return cache[key] = ans, ans\n}\n\n// create key for cache\nfunction generateKey(mainTravel, evilMatch, left, right) {\n    return (mainTravel << 8) | (evilMatch << 2) | ((left ? 1 : 0 ) << 1) | (right ? 1 : 0)\n}\n\n// for next right move, index + 1\nfunction computeNext(evil, n = evil.length, ans = new Array(n).fill(0), k = 0) {\n    for(let i = 1; i < n; i++) {\n        while((k > 0) && (evil[i] !== evil[k])) {\n            k = ans[k - 1]\n        }\n\n        if(evil[i] === evil[k]) {\n            ans[i] = ++k\n        }\n    }\n    return ans\n}\n```
['JavaScript']