Leetcode - Longest Common String

<h3>Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.</h3>
For example, if the given strings are “GeeksforGeeks” and “GeeksQuiz”, the output should be 5 as longest common substring is “Geeks”

这道题目不是Leetcode 上的。一开始觉得很难,看了答案后发现dp做简单。
dp就是这样,想不到,觉得这道题目太变态了,想到了,觉得好简单。
但是,往往想到,都是建立在,看了答案基础上的。
平常心。

My code:

public int longestCommonString(String s1, String s2) {
        if (s1 == null || s1.length() == 0)
            return 0;
        if (s2 == null || s2.length() == 0)
            return 0;
        
        int[][] dp = new int[s1.length()][s2.length()];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < s1.length(); i++) {
            if (s2.charAt(0) == s1.charAt(i)) {
                dp[i][0] = 1;
                max = 1;
            }
        }
        for (int i = 0; i < s2.length(); i++) {
            if (s1.charAt(0) == s2.charAt(i)) {
                dp[0][i] = 1;
                max = 1;
            }
        }
        
        for (int i = 1; i < s1.length(); i++) {
            for (int j = 1; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
        
        return max;
    }

就是建立一个dp[][] 数组用来记录 i, j 结尾的最长尾字符串长度。
然后一步步递推。
参考网页:
http://www.geeksforgeeks.org/longest-common-substring/

Anyway, Good luck, Richardo!

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,767评论 0 33
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,899评论 2 36
  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,322评论 0 18
  • Question: My code: My test result: 侮辱智商的题目。不爆粗口了。 **总结:简书...
    Richardo92阅读 480评论 0 1
  • 我和三岁小天使的对话 傍晚时分,小朋友和妈妈在我店门口经过,手里拿着一副自己画的彩色画,无比...
    辛夷阚秀林阅读 337评论 1 5