本文主要是介绍算法44：动态规划专练（最长公共子串题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
之前写过一篇博客是关于最长公共子序列的博客算法27：最长公共子序列（力扣1143题）——样本模型（4）_样本模型无效的条件-CSDN博客
子序列是可以删除某些字符达到的。
比如：字符串1为 a1b2c3. 字符串2为 aqvb2dcm3.
最长公共子序列就是: ab2c3.
最长公共子串就是 : b2. 公共子串，是不可以删除的
给你两个字符串，找出最长公共字符串：
这一题就是找规律，假设 两个字符串分别为 delete 和 leet。
我们发现，只要是两个字符相等，就依赖左上方的值 和 当前列的值，组成一个新的公共子串。
对不对呢？
继续假设 sea 和 eat，公共子串应该为 ea
那如果没有公共子串呢？
代码：
package code04.动态规划专项训练03;public class LeetCode712_找公共子串2 {public String maxStr(String s1, String s2) {//边界值if (s1 == null || s2 == null || s1.isEmpty() || s2.isEmpty()) {return "";}if (s1.length() == 1 && s2.length() == 1) {return s1.charAt(0) == s2.charAt(0) ? String.valueOf(s1.charAt(0)) : "";}char[] s1Str = s1.toCharArray();char[] s2Str = s2.toCharArray();String[][] dp = new String[s1.length()][s2.length()];String result = "";//s1做行，s2做列//第一行for (int i = 0; i < s2.length(); i++) {if (s1Str[0] == s2Str[i]) {dp[0][i] = String.valueOf(s1Str[0]);if (!"".equals(dp[0][i])) {result = String.valueOf(dp[0][i]);}}else {dp[0][i] = "";}}//第一列for (int i = 0; i < s1.length(); i++) {if (s1Str[i] == s2Str[0]) {dp[i][0] = String.valueOf(s2Str[0]);if (!"".equals(String.valueOf(dp[0][i]))) {result = String.valueOf(dp[0][i]);}}else {dp[i][0] = "";}}for (int index1 = 1; index1 < s1Str.length; index1++) {for (int index2 = 1; index2 < s2Str.length; index2++) {//if (s1Str[index1] == s2Str[index2]) {dp[index1][index2] = dp[index1 - 1][index2 - 1] + s1Str[index1];}else{dp[index1][index2] = "";}if (dp[index1][index2].length() > result.length()) {result = dp[index1][index2];}}}return result;}public static void main(String[] args) {/* String s1 = "eab";String s2 = "eac";*//* String s1 = "leet";String s2 = "delete";*/String s1 = "a1b2c3";String s2 = "aqvb2dcm3";LeetCode712_找公共子串2 ss = new LeetCode712_找公共子串2();System.out.println(ss.maxStr(s1, s2));}
}
这篇关于算法44：动态规划专练（最长公共子串题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
