关注
说一个时间换空间的方法, 先使用一个二维数组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
相关推荐
点赞 评论 收藏
分享
04-10 23:34
中南大学 前端工程师 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 设计人如何选offer #
97933次浏览 680人参与
# 找工作,行业重要还是岗位重要? #
6925次浏览 85人参与
# 五一之后,实习真的很难找吗? #
44507次浏览 313人参与
# 盲审过后你想做什么? #
12339次浏览 110人参与
# 领导秒批的请假话术 #
9676次浏览 74人参与
# 外包能不能当跳板? #
22042次浏览 191人参与
# 考研可以缓解求职焦虑吗 #
20568次浏览 244人参与
# 五一假期,你打算“躺”还是“卷”? #
26270次浏览 402人参与
# 面试等了一周没回复,还有戏吗 #
115254次浏览 1072人参与
# 找工作前vs找工作后的心路变化 #
7124次浏览 64人参与
# 牛友们的论文几号送审 #
27156次浏览 623人参与
# 你喜欢工作还是上学 #
37369次浏览 409人参与
# 应届生薪资多少才合理? #
3050次浏览 24人参与
# 如何缓解入职前的焦虑 #
171714次浏览 1267人参与
# 写简历别走弯路 #
714122次浏览 7849人参与
# 每人推荐一个小而美的高薪公司 #
72819次浏览 1357人参与
# 如果有时光机,你最想去到哪个年纪? #
43203次浏览 765人参与
# 硬件人,你被哪些公司给挂了 #
46489次浏览 719人参与
# 大疆的机械笔试比去年难吗 #
69568次浏览 602人参与
# 扒一扒那些奇葩实习经历 #
41606次浏览 770人参与