题解 | 最长公共子串

import java.util.*;


public class Solution {
   /**
     * 寻找两个字符串的最长公共子串(Longest Common Substring)
     * 使用动态规划方法解决
     *
     * @param str1 第一个字符串
     * @param str2 第二个字符串
     * @return 返回两个字符串的最长公共子串，如果没有则返回null
     */
    public String LCS(String str1, String str2) {
        // 检查输入参数是否有效
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return null;
        }

        // 获取两个字符串的长度
        int m = str1.length();
        int n = str2.length();

        // 创建动态规划表，dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子串
        String[][] dp = new String[m + 1][n + 1];
        String ans = ""; // 用于存储最终结果
        // 初始化动态规划表的第一列
        for (int i = 0; i <= m; i++) {
            dp[i][0] = "";
        }

        // 初始化动态规划表的第一行
        for (int j = 0; j <= n; j++) {
            dp[0][j] = "";
        }

        // 填充动态规划表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果当前字符匹配，则将公共子串延长
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + str1.charAt(i - 1);

                } else {
                    // 如果当前字符不匹配，则公共子串为空
                    dp[i][j] = "";
                }
                // 更新最长公共子串
                String tempString = dp[i][j];
                ans = ans.length() > tempString.length() ? ans : tempString;
            }
        }

        // 返回结果，如果长度为0则返回null
        return ans.length() > 0 ? ans : null;

    }
}