说一个时间换空间的方法, 先使用一个二维数组S[n][256],S[i][j]代表a串前i个字符里面有多少个ascii码为j的字符。 然后扫一遍a串就可以把这个S数组给求出来,复杂度O(n) 然后,对于b串的第i个字符c,其实我们就是想知道该字符和a串的i-i+k(k代表a串比b串长多少)子串相比到底有多少个不一样的。 因此其实就是S[i+k][c] - S[i][c]。 所以总的复杂度是O(n) 不需要DP啥的
点赞 2

相关推荐

抱抱碍事梨a:三点建议,第一点是建议再做一个项目,把自我介绍部分顶了,第二点是中南大学加黑加粗,第三点是建议加v详细交流
点赞 评论 收藏
分享
牛客网
牛客企业服务