关注
说一个时间换空间的方法, 先使用一个二维数组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
相关推荐
查看8道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
3481次浏览 82人参与
# 刚工作,应该先搞钱or搞成长? #
20888次浏览 165人参与
# 牛客AI体验站 #
15697次浏览 278人参与
# 你觉得第一学历对求职有影响吗? #
230064次浏览 1267人参与
# 如何提高实习转正率? #
85792次浏览 504人参与
# 找工作中的小确幸 #
80436次浏览 448人参与
# 实习在多还是在精 #
82820次浏览 509人参与
# 你觉得技术面多长时间合理? #
168157次浏览 1170人参与
# 牛友的春节生活 #
12254次浏览 229人参与
# 月薪多少能在一线城市生存 #
136471次浏览 898人参与
# 哪些公司对双非友好 #
207003次浏览 1163人参与
# 选了这个offer,你有没有后悔? #
738683次浏览 4472人参与
# 秋招踩过的“雷”,希望你别再踩 #
185729次浏览 1684人参与
# 备战春招/暑实,现在应该做什么? #
8101次浏览 205人参与
# 从夯到拉,锐评职场mentor #
7913次浏览 113人参与
# 实习到现在,你最困惑的一个问题 #
7133次浏览 169人参与
# 电网笔面经互助 #
59707次浏览 476人参与
# 找工作中的意难平 #
983679次浏览 6424人参与
# 制造业的秋招小结 #
143391次浏览 2089人参与
# 春招什么时候投? #
13399次浏览 211人参与
韶音科技公司氛围 665人发布