刷Lintcode最长子串问题

给出两个字符串,找到最长公共子串,并返回其长度。

样例

给出A=“ABCD”,B=“CBCE”,返回 2

1.我的想法:

双循环遍历,找出相同的子串,设置临时变量tmp记录字串长度,将tmp保存在数组中,最后在数组中找最大值。

2.需要解决的问题:

什么时候将tmp放入数组中呢? 我的想法是当A,B符号串的下一个符号不相等时,或者A,B符号串其中之一遍历到头了,这个时候将其放入。

3.遇到的困难,

针对2.我写了if判断语句,但是最后编译有问题。思来想去并不知道哪里出了错。

4.答案:

答案的思路与1.相似,只是他使用了一个矩阵,用(i-1,j-1)代表A[i-1] B[j-1]的状态。算法是如果两者相等,则(i-1,j-1)的值等于(i-2,j-2)的值加一,否则为0;这样做很巧妙,最后只需要在矩阵中找出最大值就可以了。它避免了我2.中需要判断何时存入值的问题。

5.启示:

1.可以加构一个新的数据结构来存储有用的信息,2.累积计算的思想避免了人为的择时,3.从后往前判断比从前往后判断有优势:避免了可能的溢出。参考动态规划的思想。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,357评论 0 33
  • 计算机二级C语言上机题库(南开版) 1.m个人的成绩存放在score数组中,请编写函数fun,它的功能是:将低于平...
    MrSunbeam阅读 11,543评论 1 42
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 33,238评论 18 399
  • 在文档对象模型 (DOM) 中,每个节点都是一个对象。DOM 节点有三个重要的属性: nodeName : 节点的...
    LOOK_LOOK阅读 3,759评论 0 0
  • 超级速算名人堂—7 圣 入选时间:2015-2-22 入选级别:787级 入选理由:圣,男,90后计算机专业大学生...
    V5特湘叶叶阅读 1,895评论 0 0

友情链接更多精彩内容