京东 8.27 后端面试 第三题 漂亮串 简单解法
漂亮串那题
楼主当时的解法超时了。写完才发现是 10^6的规模
因此需要O(n)解法才不超时
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);
}
} 
