解题思路

这是一个最长公共子串问题。关键点：

  1. 动态规划定义：

    • 表示以 和 结尾的最长公共子串长度
    • 注意与最长公共子序列的区别：子串必须连续

  2. 状态转移：

    • 当 时：
    • 否则：

  3. 最终结果：

    • 需要记录 数组中的最大值
    • 最大值即为最长公共子串的长度

代码

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int maxLen = 0;
        
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    maxLen = max(maxLen, dp[i][j]);
                }
            }
        }
        
        return maxLen;
    }
};

import java.util.*;

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        // write code here
        int[][] dp = new int[n + 1][m + 1];
        int maxLen = 0;
        
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(A.charAt(i-1) == B.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        
        return maxLen;
    }
}

# -*- coding:utf-8 -*-

class LongestSubstring:
    def findLongest(self, A, n, B, m):
        dp = [[0] * (m + 1) for _ in xrange(n + 1)]
        maxLen = 0
        
        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    maxLen = max(maxLen, dp[i][j])
        
        return maxLen

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：，需要填充整个 表
  • 空间复杂度：，需要二维 数组