java clean solution
Can not solve it during the contset.  The problem can use a tree structure to visualize it\n\nThe picture from @hiepit was really helpful. I get intuition from 
Can not solve it during the contset.  The problem can use a tree structure to visualize it\n\nThe picture from @hiepit was really helpful. I get intuition from this picture\nThe link:\nhttps://leetcode.com/problems/find-all-good-strings/discuss/555591/JavaC%2B%2B-Memoization-DFS-and-KMP-with-Picture-Clean-code-~-16ms\n\n\nI used visit boolean to recodrd if we visit\n\nKMP prefix is used to check if we reach the end of the substring(we found evil) \n(For more KMP related usage, problem 28 is a good example and practice )https://leetcode.com/problems/implement-strstr/discuss/557044/java-kmp-sol\nProblem 1376 would also be a good practice problem for kmp+dfs\n\nboolean 1 and boolean2 is used to check the range (less than s1 or larger than s2)\n\nuse dfs (like a tree structure) for searching and memorize them\n\nFeel free to ask any question\n\n\n```\nclass Solution {\n    int mod=1000000007;\n    int pre[];\n    long dp[][][][];\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        if(s1.equals(s2)){//dealing the equal case\n            if(s1.indexOf(evil)!=-1)return 0;\n            return 1;\n        }\n       \n        pre=pre(evil);\n       \n        dp=new long[s1.length()][s2.length()][2][2];\n        \n        for(int i=0;i<dp.length;i++){\n            for(int j=0;j<dp[0].length;j++){\n                for(int k=0;k<dp[0][0].length;k++)Arrays.fill(dp[i][j][k],-1);\n            }\n        }\n        return (int)(dfs(evil,s1,s2,0,0,1,1));\n    }\n    \n    public long dfs(String evil,String s1,String s2,int i,int j,int state1,int state2){\n        if(j==evil.length())return 0;\n        if(i==s1.length())return 1;\n        \n        if(dp[i][j][state1][state2]!=-1)return dp[i][j][state1][state2];\n        \n        long res=0;\n        char small=s1.charAt(i);\n        char big=s2.charAt(i);\n        \n        for(int x=0;x<26;x++){\n            char c=(char)(x+\'a\');\n            int news1=state1;\n            int news2=state2;\n            \n            if(state1==1&&state2==0){\n                if(c<small)continue;\n                if(c!=small)news1=0;\n            }\n            else if(state1==0&&state2==1){\n                if(c>big)continue;\n                if(c!=big)news2=0;\n            }\n            else if(state1==1&&state2==1){\n                if(c<small||c>big)continue;\n                if(c!=small)news1=0;\n                if(c!=big)news2=0;\n            }\n            else{//0 0\n                \n            }\n            \n            \n            //kmp part\n            int evinIndex=j;\n            if(c==evil.charAt(evinIndex)){\n                evinIndex++;\n            }else{\n                if(evinIndex==0){\n                    \n                }else{\n                    while(evinIndex!=0&&evil.charAt(evinIndex)!=c)evinIndex=pre[evinIndex-1];\n                    if(c==evil.charAt(evinIndex))evinIndex++;\n                }\n            }\n            //////////////////////////\n            \n            res+=dfs(evil,s1,s2,i+1,evinIndex,news1,news2);\n            res%=mod;\n        }\n        dp[i][j][state1][state2]=res;\n        return res;\n    }\n    \n    public int[] pre(String p){\n        int pre[]=new int[p.length()];\n        int l=0,r=1;\n        while(r<p.length()){\n            if(p.charAt(l)==p.charAt(r)){\n                pre[r]=l+1;\n                l++;r++;\n            }else{\n                if(l==0)r++;\n                else l=pre[l-1];\n            }\n        }\n        return pre;\n    }\n}\n```
[]