#每日一面BAT#第2题:三字符构成的字符串个数


每日一面BAT

仅由三个字符A、B、C构成字符串,且字符串任意相邻三个元素不能完全相同。如“ACCCAB”不合法,“ABBCBCA”合法。求满足条件的长度为n的字符串个数。假定不考虑整数溢出,要求时间和空间复杂度不高于O(N)。

提示:
1、考虑使用动态规划,将长度为N的字符串个数表示成长度为N-1的字符串个数的递归关系;
2、使用滚动数组降低空间复杂度;
3、矩阵乘幂降低时间复杂度。
已邀请:

邹博 - 学而时习之

赞同来自: taoyi3513 hecate iphyer skyitachi 咬咬 tianjie 流火星空更多 »


参考答案解析:

1.png

2.png

3.png

4.png

5.png

6.png

7.png

要回复问题请先登录注册

返回顶部