京东 8.27 后端面试 第三题 漂亮串 简单解法

class Solution {
    // G(n) 代表 长度为n的字符串中不同的漂亮串的个数
    // N(n) 代表 长度为n的字符串中不出现任何red子串的个数
    // G（n）可以拆解成以下两部分：
    // 当前 n-1个字符形成了漂亮串时： 此时 形成了 G(n-1)*26个新的满足要求的串。
    // 当前 n-1个字符没有形成漂亮串时：因为多出来的一个字符，有可能与前面两个字符串形成 red，此时就要求 前 n-3 个字符有且只有一个red
    // 因此我们需要求前 n-3 个字符串中 有且仅有一个red的不同字符串个数：
    // 这个等于  前 n-3 个字符串的所有种类， 减去 前n-3个字符串中所有漂亮字符串个数，再减去 n-3个字符串中 所有不存在的red子串的个数，即N（n）
    // 即 = 26^(n-3) - G(n-3) - N(n-3)
    // 另外 N(n) 可以通过递推公式 N（n） = N(n -1)*26 - N(n-3)得到

    public  int getres(int n) {
        Long MOD = 1000000007L;
        ArrayList<Long> G = new ArrayList<>();
        ArrayList<Long> N = new ArrayList<>();
        ArrayList<Long> P = new ArrayList<>();
        N.addAll(Arrays.asList(1L,26L,26*26L));
        G.addAll(Arrays.asList(0L,0L,0L,0L,0L,0L));
        P.add(1L);
        for(int i=3;i<=n;i++){
            N.add((N.get(i-1)*26 - N.get(i-3))%MOD);
        }
        // 26的几次幂 列表
        for(int i=0;i <n;i++){
            P.add(P.get(i)*26 %MOD);
        }

        for(int i=6;i<=n;i++){
            G.add((G.get(i-1)*26 + P.get(i-3) - G.get(i-3) - N.get(i-3)) % MOD);
        }
        return (int)((G.get(n)+MOD)%MOD);
    }
}