1397. 找到所有好字符串 KMP+数位dp

1397. 找到所有好字符串

给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回 好字符串 的数目。

好字符串 的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。

由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。

示例 1：

输入：n = 2, s1 = "aa", s2 = "da", evil = "b"
输出：51 
解释：总共有 25 个以 'a' 开头的好字符串："aa"，"ac"，"ad"，...，"az"。还有 25 个以 'c' 开头的好字符串："ca"，"cc"，"cd"，...，"cz"。最后，还有一个以 'd' 开头的好字符串："da"。

示例 2：

输入：n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
输出：0 
解释：所有字典序大于等于 s1 且小于等于 s2 的字符串都以 evil 字符串 "leet" 开头。所以没有好字符串。

示例 3：

输入：n = 2, s1 = "gx", s2 = "gz", evil = "x"
输出：2

提示：

• s1.length == n
• s2.length == n
• s1 <= s2
• 1 <= n <= 500
• 1 <= evil.length <= 50
• 所有字符串都只包含小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-good-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，就是花了好几个小时，开始没想到KMP，后面想到了但是不知道怎么写，现找板子贴的

 方法：KMP+数位dp

1. 由于涉及字符串匹配，所以需要用到KMP,就是ABCABD，这种字符串，如果给定 ABCABC,最后一个C要配到 ABC 的位置

2. 数位 dp 和前面几天写的类似，都是上限，下限，这部分不再细讲

2. 特色部分：匹配长度全的情况不能记录，因为题目要求不能全匹配；dp二维条件为匹配长度，即为到达某个位置 i 时，在匹配长度为 j 的情况下，后续能找到多少好字符串

class Solution {
        long[][] dp;
        char[] down;
        char[] up;
        int n;
        char[] devil;
        int[] next;
        long MOD = (long) (1e9+7);
        public int findGoodStrings(int n, String s1, String s2, String evil) {
            this.n = n;
            down = s1.toCharArray();
            up = s2.toCharArray();
            devil = evil.toCharArray();
            next = getNext(evil);
            dp = new long[n][devil.length];
            for(int i = 0;  i< n; i++) Arrays.fill(dp[i],-1);
            int ans = (int) dfs(true,true,0,0);
            return ans;
        }
 
 
        public  int[] getNext(String ps) {
               char[] p = ps.toCharArray();
       int n = p.length;
       int[] next = new int[n];
       int i = 0;
       int j = -1;
       next[0] = -1;
       while(i1){
           if(j==-1 || p[i]==p[j]){
               next[++i]=++j;
           }else{
               j = next[j];
           }
       }
       next[0]=0;
       return next;
 
        }
 
        private long dfs(boolean limitUp, boolean limitDown, int index, int matchDevil){
            if(index==n) return 1;
            if(!limitUp && !limitDown && dp[index][matchDevil]!=-1) return dp[index][matchDevil];
            long ans = 0;
            char min = limitDown?down[index]:'a';
            char max = limitUp?up[index]:'z';
            for(char i = min; i <= max; i++){
                int matchEvilLen = matchDevil;
                if(i==devil[matchDevil]){
                    matchEvilLen = matchDevil+1;
                }else {
                    //关键：KMP不匹配的情况，需要一直往前搜索，而不能找不到直接结束
                    while (next[matchEvilLen] > 0 && devil[next[matchEvilLen]] != i) {
                        matchEvilLen = next[matchEvilLen];
                    }
                    if (devil[next[matchEvilLen]] == i) {
                        matchEvilLen = next[matchEvilLen] + 1;
                    } else {
                        matchEvilLen = 0;
                    }
                }
 
                if(matchEvilLen==devil.length)
                    continue;
                ans = (ans + dfs(limitUp&&i==max,limitDown&&i==min,index+1,matchEvilLen)%MOD)%MOD;
            }
 
            if(!limitUp && !limitDown) dp[index][matchDevil] =  ans;
            return ans;
        }
    }