Solution ind All Good Strings
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    private $mod = 1000000007;\n    private $cache = [];\n\n    /**\n     * @param Integer $n\n     * @param String $s1\n     * @param String $s2\n     * @param String $evil\n     * @return Integer\n     */\n    function findGoodStrings($n, $s1, $s2, $evil) {\n        $this->cache = array_fill(0, 1 << 17, -1);\n        return $this->dfs(0, 0, $n, $s1, $s2, $evil, true, true, $this->computeNext($evil));\n    }\n\n    function dfs($mainTravel, $evilMatch, $n, $s1, $s2, $evil, $left, $right, $next, &$ans = 0) {\n        if ($evilMatch === strlen($evil)) {\n            return 0;\n        }\n        if ($mainTravel === $n) {\n            return 1;\n        }\n        \n        $key = $this->generateKey($mainTravel, $evilMatch, $left, $right);\n        if ($this->cache[$key] !== -1) {\n            return $this->cache[$key];\n        }\n        \n        $start = $left ? ord($s1[$mainTravel]) : 97; // \'a\'\n        $end = $right ? ord($s2[$mainTravel]) : 122; // \'z\'\n        \n        for ($i = $start; $i <= $end; $i++) {\n            $code = chr($i);\n            $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            $ans += $this->dfs($mainTravel + 1, $m, $n, $s1, $s2, $evil, $left && ($i === $start), $right && ($i === $end), $next);\n            $ans %= $this->mod;\n        }\n        \n        return $this->cache[$key] = $ans;\n    }\n\n    function generateKey($mainTravel, $evilMatch, $left, $right) {\n        return ($mainTravel << 8) | ($evilMatch << 2) | (($left ? 1 : 0 ) << 1) | ($right ? 1 : 0);\n    }\n\n    function computeNext($evil) {\n        $n = strlen($evil);\n        $ans = array_fill(0, $n, 0);\n        $k = 0;\n\n        for ($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\n        return $ans;\n    }\n}\n\n```
['PHP']